This is the companion notebook to the introductory course on simple portfolio construction and performance metrics. It contains simple examples of portfolio backtesting. The structures of this section will be used later on in the course.
\(\rightarrow\) ABOUT THE NOTEBOOK:
- the code chunks are sequential. They must be executed in the correct order.
- text between stars appears in bold in html format.
A glimpse at the S&P500
The S&P500 is one of the most widely scrutinised index in the US Equity investment space. It serves very often as benchmark. The purpose of this section is to unveil a few of its statistical properties and to use the highcharter package for highchart rendering in R.
Prices
We start by loading the packages and downloading the data. For technical reasons, we download the series of the ETF replicating the S&P500 (SPY ticker).
if(!require(highcharter)){install.packages("highcharter")} # Package for nice financial graphs
if(!require(scales)){install.packages("scales")} # Package for graph scales
library(tidyverse) # The data wrangling package
library(plotly) # For interactive graphs
library(lubridate) # For data management
library(quantmod) # The package that eases the downloading of financial data
library(highcharter) # The package for financial time-series plots
min_date <- "1980-01-01"
max_date <- "2021-05-05"
prices <- getSymbols("SPY", src = 'yahoo', # Yahoo source (ETF ticker) ^GSPC
from = min_date,
to = max_date,
auto.assign = TRUE,
warnings = FALSE) %>%
map(~Ad(get(.))) %>%
reduce(merge) %>%
`colnames<-`("SPY")
Then, we turn to plotting, using highchart format. We underline that this package works with special xts (R extensible time-series) format. We point to the package reference for more details on this subject:
- https://jkunst.com/highcharter/
- https://www.highcharts.com/blog/tutorials/highcharts-for-r-users/
- https://cran.r-project.org/web/packages/highcharter/index.html
highchart(type = "stock") %>%
hc_title(text = "Evolution of the SPY") %>%
hc_add_series(prices)
A nice feature of highcharts is that they allow the user to change the observation period and see the values of points on the curve.
Returns
Next, we turn to the distribution of returns.
returns <- prices %>% # Formula for returns
data.frame(Date = index(.)) %>% # Adding the Date as a column
mutate(SPY = SPY / dplyr::lag(SPY) - 1) %>% # Returns
na.omit() # Removing NA rows
m <- mean(returns$SPY) # Average daily return
s <- sd(returns$SPY) # Volatility = sd of daily returns
returns %>% ggplot() + # Plot
geom_histogram(aes(x = SPY, y = ..density..), bins = 100, alpha = 0.6) + theme_light() +
stat_function(fun = dnorm, args = list(mean = m, sd = s), aes(color = "Gaussian")) +
theme(legend.position = c(0.7, 0.7))

We plot the Gaussian density with parameters corresponding to the sample mean and standard deviation. Small grey rectangles around \(\pm 0.05\) indicate that large positive and negative returns occur more often than estimate by the Gaussian law: the tails of their distribution are notoriously heavy.
Volatility
Finally, we take a dynamic look at the volatility. We take a frugal approach; much more elegant methods are presented in Section 4.5 of Reproducible Finance by Jonathan Regenstein, as well as the roll_sd() function used in http://www.reproduciblefinance.com/drafts/post/vix-and-realized-volatility-updating-our-previous-work/
nb_days <- 63 # 63 days roughly equivalent to 3 months
vol <- 0 # Initialisation
for(i in 1:(nrow(returns) - nb_days + 1)){ # Loop on dates: not elegant!
vol[i] <- sd(returns$SPY[i:(i + nb_days - 1)]) # Forward vol computed on rolling window of nb_days
}
Date <- returns$Date[nb_days:nrow(returns)] # Vector of dates
vol <- data.frame(vol*sqrt(252)) # Vector inside a dataframe
rownames(vol) <- Date # Change the index of the dataframe
highchart(type = "stock") %>% # Code for the plot
hc_title(text = "Evolution of realized volatility") %>%
hc_add_series(as.xts(vol))
Clearly the graph shows periods of low volatility and clusters of high market turbulence (crashes, most of the time). Returns are therefore not stationary. The properties we exhibited for the S&P500 are also true at the individual stock level.
In the next sections, we turn to the core topic of portfolio backtesting.
Data
First, letās start with the preprocessing of the data.
We first import and arrange the data. The data consists of monhtly financial information pertaining to 30 large US firms. They are characterised by their ticker symbol:
| AAPL (Apple) |
GE (General Electric) |
ORCL (Oracle) |
| BA (Boeing) |
HD (Home Depot) |
PFE (Pfizer) |
| BAC (Bank of America) |
IBM |
PG (Procter & Gamble) |
| C (Citigroup) |
INTC (Intel) |
T (AT&T) |
| CSCO (Cisco) |
JNJ (Johnson & Johnson) |
UNH (United Health) |
| CVS (CVS Health) |
JPM (JP Morgan) |
UPS |
| CVX (Chevron) |
K (Kellogg) |
VZ (Verizon) |
| D (Dominion Energy) |
MCK (McKesson) |
WFC (Wells Fargo) |
| DIS (Disney) |
MRK (Merck) |
WMT (Walmart) |
| F (Ford) |
MSFT (Microsoft) |
XOM (Exxon) |
There are 7 attributes: closing price (Close), market capitalisation in M$ (Mkt_Cap), price-to-book ratio (P2B), 1 month volatility (Vol_1M), 1 month relative strength index (RSI_1M), debt-to-equity ratio (D2E) and profitability margin (Prof_Marg).
Finally, the time range is 2000-2021.
load("data.RData") # Loading the data: IF DIRECTORY OK!
data <- data %>% arrange(Date,Tick) # Ranked first according to date and then stocks
summary(data) # Descriptive statistics
Tick Date Close Vol_1M Mkt_Cap P2B D2E
AAPL : 255 Min. :1999-12-31 Min. : 0.217 Min. : 5.867 Min. : 4467 Min. : 0.1013 Min. : 0.00
BA : 255 1st Qu.:2005-03-31 1st Qu.: 19.166 1st Qu.: 15.970 1st Qu.: 67392 1st Qu.: 1.4223 1st Qu.: 31.83
BAC : 255 Median :2010-07-30 Median : 32.307 Median : 21.835 Median : 137516 Median : 2.3494 Median : 66.76
C : 255 Mean :2010-07-30 Mean : 49.261 Mean : 27.054 Mean : 160615 Mean : 11.1931 Mean : 218.70
CSCO : 255 3rd Qu.:2015-11-30 3rd Qu.: 57.307 3rd Qu.: 31.894 3rd Qu.: 210966 3rd Qu.: 4.2259 3rd Qu.: 213.09
CVS : 255 Max. :2021-02-26 Max. :442.987 Max. :268.563 Max. :2255969 Max. :1678.9053 Max. :14585.61
(Other):6120
Prof_Marg ESG_rank
Min. :-106.260 Min. : 7.317
1st Qu.: 5.008 1st Qu.: 54.237
Median : 10.312 Median : 72.222
Mean : 11.712 Mean : 68.352
3rd Qu.: 19.171 3rd Qu.: 86.364
Max. : 145.583 Max. :100.000
NA's :5214
tick <- unique(data$Tick) # Set of assets
t_all <- unique(data$Date) # Set of dates
N <- n_distinct(data$Tick) # Number of stocks
This simple table shows a possible outlier for the P2B variable. The maximum value is clearly out of range.
Next, we format the data for future use. Notably, we compute & store returns.
data <- data %>%
group_by(Tick) %>% # Grouping: returns computed stock-by-stock
mutate(Return = Close / dplyr::lag(Close) - 1) %>% # Adding returns
ungroup()
returns <- data %>% # Take data
select(Tick, Date, Return) %>% # Select 3 columns
pivot_wider(names_from = Tick, values_from = Return) # Put them into 'matrix' format
returns # Show the returns
What students often doā¦
Now, letās consider the usual Markowitz allocation subject to the budget constraint \(\textbf{w}'\textbf{1}=1\):
\[\text{max} \ \textbf{w}'\boldsymbol{\mu} - \frac{\gamma}{2}\textbf{w}'\boldsymbol{\Sigma}\textbf{w}, \quad \text{s.t.} \quad \textbf{w}'\textbf{1}=1 \] with Lagrangian: \[L(\textbf{w})=\textbf{w}'\boldsymbol{\mu} - \frac{\gamma}{2}\textbf{w}'\boldsymbol{\Sigma}\textbf{w}+\delta (\textbf{w}'\textbf{1}-1)\] so that \[\frac{\partial L}{\partial \textbf{w}}=\boldsymbol{\mu}-\gamma\boldsymbol{\Sigma}\textbf{w}+\delta\textbf{1}=0 \quad \Rightarrow \quad \textbf{w}=\gamma^{-1}\boldsymbol{\Sigma}^{-1}(\boldsymbol{\mu}+\delta \textbf{1}),\] where \(\delta\) is chosen to satisfy the budget constraint. A particular case is the minimum variance portfolio which corresponds to \(\boldsymbol{\mu}=\textbf{1}\): the optimal portfolio is proportional to \(\boldsymbol{\Sigma}^{-1} \textbf{1}\).
Sigma <- returns %>% # Covariance matrix
select(-Date) %>%
cov(use = "complete.obs")
Sigma[1:9,1:9] %>% round(3) # A quick look at Sigma
AAPL BA BAC C CSCO CVS CVX D DIS
AAPL 0.013 0.002 0.003 0.004 0.004 0.001 0.002 0.000 0.003
BA 0.002 0.009 0.004 0.006 0.003 0.002 0.003 0.001 0.003
BAC 0.003 0.004 0.013 0.011 0.003 0.002 0.002 0.001 0.004
C 0.004 0.006 0.011 0.015 0.005 0.002 0.003 0.001 0.005
CSCO 0.004 0.003 0.003 0.005 0.009 0.001 0.002 0.000 0.003
CVS 0.001 0.002 0.002 0.002 0.001 0.006 0.002 0.001 0.002
CVX 0.002 0.003 0.002 0.003 0.002 0.002 0.004 0.001 0.002
D 0.000 0.001 0.001 0.001 0.000 0.001 0.001 0.002 0.001
DIS 0.003 0.003 0.004 0.005 0.003 0.002 0.002 0.001 0.006
Min_var_weights <- solve(Sigma) %*% rep(1,N) # Proportional weights
Min_var_weights <- Min_var_weights / sum(Min_var_weights) # Exact (scaled) weights
bind_cols(tick, Min_var_weights) %>%
ggplot(aes(x = Min_var_weights, y = tick)) + # Plot
geom_col(alpha = 0.5) + theme_light()

Naturally, the stocks with super low volatility (Disney, Walmart) are favored! Letās see when the weights are driven by the mean returnsā¦
mu <- returns %>% # Mean vector
select(-Date) %>% # Remove date
colMeans(na.rm = T)
Marko_weights <- solve(Sigma) %*% mu # Proportional weights
Marko_weights <- Marko_weights / sum(Marko_weights) # Exact (scaled) weights
bind_cols(tick, Marko_weights) %>%
ggplot(aes(x = Marko_weights, y = tick)) + # Plot
geom_col(alpha = 0.5) + theme_light()

AAPL and UNH have high returns => high weights.
Now letās look at 2 ways of processing these weights into portfolio values.
w_matrix <- matrix(Marko_weights,
ncol = N, nrow = length(t_all) - 1, byrow = T) # Weight matrix
(rowSums((returns %>% select(-Date)) * w_matrix) + 1) %>% # Simple product = element-wise
na.omit() %>% # Remove missing points
cumprod() %>% round(3) # Cumulative product + rounding
[1] 0.957 0.895 0.931 0.933 0.927 0.996 0.985 1.097 1.085 1.095 1.101 1.209 1.236 1.256 1.300 1.359 1.310
[18] 1.316 1.412 1.411 1.312 1.274 1.359 1.405 1.516 1.526 1.673 1.898 1.879 1.858 1.702 1.729 1.671 1.593
[35] 1.538 1.607 1.639 1.564 1.597 1.630 1.781 1.846 1.871 1.886 1.835 1.928 1.859 1.954 1.960 2.043 2.138
[52] 2.111 2.240 2.366 2.368 2.516 2.706 2.904 3.293 3.341 3.570 3.697 3.769 3.665 3.762 3.857 4.055 4.219
[69] 4.486 4.718 4.957 5.056 5.044 5.060 4.884 4.965 4.759 4.843 5.204 5.171 5.360 5.560 5.720 5.700 5.829
[86] 5.894 6.004 6.103 6.269 6.035 6.066 6.167 6.389 7.167 8.004 8.508 7.763 7.271 7.284 7.540 8.156 7.465
[103] 7.650 8.099 7.535 7.358 7.195 7.863 8.345 7.881 7.529 7.940 8.635 9.435 9.963 8.916 9.034 9.398 10.201
[120] 11.351 11.002 11.670 12.086 11.940 11.344 11.201 11.591 11.362 12.097 12.296 11.989 12.214 12.611 13.273 13.464 13.812
[137] 14.252 14.058 14.536 14.963 14.356 14.518 14.638 15.176 15.599 16.918 17.804 17.594 18.055 19.206 18.919 19.155 18.661
[154] 17.938 18.058 17.509 17.361 17.620 18.328 19.586 19.818 20.029 21.619 22.017 22.751 23.817 25.805 25.872 26.049 27.052
[171] 29.119 28.340 29.926 30.933 29.912 31.684 32.336 34.675 36.337 37.271 37.692 38.300 37.915 37.414 38.274 38.052 38.422
[188] 35.745 36.012 37.135 36.997 37.023 37.860 37.233 39.859 38.358 39.147 40.790 42.238 41.284 42.089 43.308 45.886 47.406
[205] 50.376 53.211 53.917 56.048 58.458 59.210 63.626 65.449 63.280 69.919 76.063 78.350 83.468 80.938 76.859 77.800 79.071
[222] 80.365 86.609 92.206 94.659 96.311 102.447 90.073 87.358 92.111 95.476 99.186 95.228 99.665 97.140 103.540 104.853 108.992
[239] 110.806 115.953 111.383 97.044 89.036 102.187 103.793 99.388 95.844 100.039 93.242 81.467 99.422 99.446 99.910 98.918
The above code is ugly. Because the data is neatly ordered, we can do better! Letās add a new column to the data.
data %>%
select(Tick, Date, Return) %>% # Keep only necessary cols
bind_cols(w_Marko = rep(Marko_weights, length(t_all))) # Bind cols: beware to the order!
Now we can add benchmark weights and proceed.
p <- data %>%
select(Tick, Date, Return) %>%
bind_cols(w_Marko = rep(Marko_weights, length(t_all))) %>%
mutate(w_benchmark = 1/30) %>% # Add benchmark weights 1/N
pivot_longer(cols = c(w_Marko, w_benchmark), # Pivot to tidy
names_to = "Portfolio",
values_to = "Weight") %>%
group_by(Date, Portfolio) %>% # Group to compute portf return
summarise(Return = sum(Weight * Return)) %>% # Portf return, date-by-date
ungroup() %>% # Ungroup
na.omit() %>% # Remove outliers
group_by(Portfolio) %>% # Group along the 2 portfolios
mutate(Value = cumprod(1+Return)) %>% # Compute portfolio values
ggplot(aes(x = Date, y = Value, color = Portfolio)) + # Plot
geom_line() + theme_light() + scale_y_log10() +
scale_color_manual(values = c("#706C66", "#0A5B90"), labels = c("Benchmark", "Markowitz")) +
theme(legend.position = c(0.3,0.7))
ggplotly(p, width = 900)
Given the log-scale: is this reasonably realistic? Obvious answer: NO! The weights have been chosen with knowledge of the trajectory!!! Also: portfolio managers update the weightsā¦
A universe of functions
Backtesting portfolio strategies is usually simple at first, but becomes more intricate when many options are considered. To keep things simple, it is more efficient to work with functions. Functions help compartmentalise the different tasks of the process. We will build functions that compute portfolio weights and others that evaluate the performance metrics of the strategies. While we will usually work with a loop on backtesting dates, it is possible to build functions that directly generate portfolio returns (see below: the map() function).
By definition, a portfolio is a choice of weights that sum to one. Below, we implement two classical weighting schemes: the uniform portfolio (EW = equal weights) and the maximum Sharpe ratio portfolio (MSR). The latter is more complicated and requires inputs: namely the column vector of (expected) mean \(\mu\) and covariance matrix \(\Sigma\) of the assets. For simplicity, we will estimate them using sample moments - even though this is known to be a bad choice. This requires an additional argument in the function: the assetsā past returns. The MSR weights are \(w=\frac{\Sigma^{-1}\mu}{1'\Sigma^{-1}\mu}\). Both \(\mu\) and 1 are vectors here.
weights_msr <- function(returns){ # returns will refer to PAST returns
m <- apply(returns, 2, mean) # Vector of average returns
sigma <- cov(returns) # Covariance matrix
w <- solve(sigma) %*% m # Raw weights
return(w / sum(w)) # Returns normalised weights
}
weights_ew <- function(returns){ # We keep the same syntax for simplicity
N <- length(returns[1,]) # Number of assets
return(rep(1/N,N)) # Weight = 1/N
}
We are now ready to proceed with the initialisation of the variables that will use in the main loop.
sep_date <- as.Date("2010-01-01") # This date separates in-sample vs out-of-sample
t_oos <- t_all[t_all > sep_date] # Out-of-sample dates (i.e., testing set)
portf_weights <- matrix(0, nrow = length(t_oos), # Will store portfolio weights
ncol = length(tick))
portf_returns <- c() # Initialize portfolio returns
At last, we can proceed to the main loop. A note of caution: both in the weighting scheme functions and in the loop below, we assume well defined (finite, i.e., non NA) data. Obviously, feeding NA data in the system will produce NA outputs. There are only four steps in the loop:
- extract the data
- compute portfolio weights
- compute realised returns
- derive the return of the portfolio
for(t in 1:length(t_oos)){
temp_data <- returns %>% filter(Date < t_oos[t]) # 1) Extracting past data: expanding window!
portf_weights[t,] <- temp_data %>% # 2) Take this past data
select(-Date) %>% # Take out the date column
na.omit() %>% # Remove missing points
weights_msr() # Appply the weighting scheme function
realised_returns <- returns %>% # 3) Take returns
filter(Date == t_oos[t]) %>% # Keep only current date
select(-Date) # Take out the date column
portf_returns[t] <- sum(portf_weights[t,] * realised_returns) # 4) Compute the return
}
In the above backtest, the amount of data considered to form the portfolio decision increases with time (expanding window). It is easy to fix the number of data point at each step and proceed on rolling windows (exercise). Likewise, switching from MSR to EW is immediate (just change the weighting function).
The main output is the vector of portfolio returns. We can easily plot the evolution of the portfolio through time.
port <- data.frame(Date = t_oos,
Portfolio = cumprod(1+portf_returns)) # Portf. values via cumulative product
port %>% ggplot() + theme_light() +
geom_line(aes(x = Date, y = Portfolio)) # Plot

Below, we create a function that takes a series of returns as input and provides a few simple performance metrics.
perf_met <- function(returns){
avg_ret <- mean(returns, na.rm = T) # Arithmetic mean
vol <- sd(returns, na.rm = T) # Volatility
Sharpe_ratio <- avg_ret / vol # Sharpe ratio
VaR_5 <- quantile(returns, 0.05) # Value-at-risk
met <- data.frame(avg_ret, vol, Sharpe_ratio, VaR_5) # Aggregation of all of this
rownames(met) <- "metrics"
return(met)
}
perf_met(portf_returns) # Let's test on the actual returns
Note: the values are not annualised. The annualisation can be directly coded into the function. A heuristic way to proceed is to multiply average returns by 12 and volatilities by \(\sqrt{12}\) - though this omits the compounding effect. These simplifications are ok if they are used to compare strategies. The Value at Risk is nonetheless dependent on the return horizon and cannot be proxied so simply.
An important indicator is the turnover of the portfolio: it assesses asset rotation and thus impacts transaction costs. Simple turnover computes average absolute variation in portfolio weights: \(\text{Turn}=\frac{1}{T}\sum_{t=2}^T\sum_{n=1}^N|w_t^n-w_{t-1}^n|\). Full turnover takes into account the variation of the weights between rebalancing dates: \(\text{Turn}=\frac{1}{T}\sum_{t=2}^T\sum_{n=1}^N|w_t^n-w_{t-}^n|\), where \(t-\) is the time just before the rebalancing date.
turnover_simple <- function(weights, t_oos){
turn <- 0
for(t in 2:length(t_oos)){ # Loop on dates
turn <- turn + sum(abs(weights[t,] - weights[t-1,])) # Variation in weights
}
return(turn/(length(t_oos)-1)) # BEWARE: monthly value!
}
turnover_simple(portf_weights, t_oos) # Simple turnover!
[1] 0.2189094
Below, we switch to the full definition of the turnover. In this case, the variation in weights is adjusted because the weight prior to rebalancing have drifted.
turnover_full <- function(weights, asset_returns, t_oos){
turn <- 0
for(t in 2:length(t_oos)){
realised_returns <- returns %>% filter(Date == t_oos[t]) %>% select(-Date)
prior_weights <- weights[t-1,] * (1 + realised_returns) # Before rebalancing
turn <- turn + apply(abs(weights[t,] - prior_weights/sum(prior_weights)),1,sum)
}
return(turn/(length(t_oos)-1))
}
asset_returns <- returns %>% filter(Date > sep_date) # Asset returns over the experiment
turnover_full(portf_weights, asset_returns, t_oos) # Real turnover
[1] 0.3014361
Note that the turnover is computed at the monthly frequency. The second value is always more realistic; in this case it is substantially higher compared to the simplified proxy. For the sake of compactness, the turnover should be included in the perf_met() function.
Extensions
Comparing strategies
An important generalisation of the above framework is to consider more than one strategy. Comparisons are commonplace in the asset management industry: obviously, people look for the best strategy (according to particular goals, beliefs, and preferences). Below, we show how this can be handled. We will compare the two strategies that we mentionned above. First, we need to re-initiate the variables because their dimension will change (NOTE: an alternative route would be to work with lists).
Tt <- length(t_oos) # Nb of computation dates
# Avoid T because T = TRUE!
nb_port <- 2 # Nb of portfolios
portf_weights <- array(0, dim = c(Tt, nb_port, length(tick))) # Store weights
portf_returns <- matrix(0, nrow = Tt, ncol = nb_port) # Store returns
Second, we embed all weighting schemes into one single function.
weights_multi <- function(returns, j){ # Strategies are indexed by j
if(j == 1){ # j = 1 => MSR
return(weights_msr(returns))
}
if(j == 2){ # j = 2 => EW
N <- length(returns[1,])
return(rep(1/N,N))
}
}
We decided to recode the EW strategy, but we could have used the weights_ew() function instead. Finally, the main loop is only marginally different from the single strategy loop.
for(t in 1:length(t_oos)){
temp_data <- returns %>%
filter(Date < t_oos[t]) %>% # Same first step
na.omit() %>%
select(-Date)
realised_returns <- returns %>% # Same third step: returns
filter(Date == t_oos[t]) %>%
select(-Date)
for(j in 1:nb_port){ # This is the novelty: we loop on the strategies
portf_weights[t,j,] <- weights_multi(temp_data, j) # The weights' function is indexed by j
portf_returns[t,j] <- sum(portf_weights[t,j,] * realised_returns)
}
}
apply(portf_returns, 2, perf_met) %>% # Taking perf metrics
unlist() %>% # Flattening the list
matrix(nrow = 2, byrow = T) %>% # Ordering them
`colnames<-`(c("avg_ret", "vol", "SR", "VaR")) %>% # Adding column names
data.frame() # Converting to dataframe
apply(portf_weights, 2, turnover_simple, t_oos = t_oos) %>% unlist()
[1] 0.2189094 0.0000000
We recall the order of strategies: MSR first (line) and EW second (line).
Again, turnover should (and will) be added to the performance metric function. Since uniform weights are constant, their simplified turnover is zero. In practice, that is not the case because weights evolve according to asset returns. The adjustment would imply only a small turnover.
There is a well-documented substantial difference between the two weigting schemes in terms of asset rotation. The MSR that we compute is clearly not competitive: even before transaction costs, its Sharpe ratio is smaller than that of the EW portfolio (see DeMiguel et al.Ā (2009) for further evidence on the robustness of the EW portfolio).
Make do without loops: functional programming
Finally, we show how to bypass the loop over dates. While this is not useful on small datasets, it can save time on large databases because loops are notoriously time-consuming. Below, we show how to proceed with the map() function in the simple case with only one strategy.
# We create a function that will compute returns for each date:
port_map <- function(t_oos, returns, weight_func){ # Weighting function as argument!
temp_data <- returns %>% filter(Date < t_oos) # Still expanding window...
portf_weights <- temp_data %>%
select(-Date) %>%
na.omit() %>%
weight_func()
realised_returns <- returns %>%
filter(Date == t_oos) %>%
select(-Date)
return(sum(portf_weights * realised_returns))
}
# the map() function does it all!
portf_returns <- t_oos %>% # The variable over which we loop
map(~port_map(.x,
returns = returns,
weight_func = weights_msr) # MSR weights
) %>% # Is sent to the map() function
unlist() # The output is flattened
perf_met(portf_returns) # Compute the perf metrics
Characteristics-based portfolio choice
In this section, we start the chapter of strategies based on firm characteristics (features). As an illustration, we check a well-documented (though still controversial) anomaly: the size effect. We build two portfolios: in the first (resp. second) one, we invest in the firms that have a below (resp. above) median market capitalisation. The first portfolio will be a āsmallā portfolio and the second one a ālargeā one. Stocks are equally-weighted inside the portfolios.
First, we prepare the variables and define the weight function.
nb_port <- 2 # Nb of portfolios
portf_weights <- array(0, dim = c(Tt-1, nb_port, length(tick))) # Where we store weights
portf_returns <- matrix(0, nrow = Tt-1, ncol = nb_port) # Where we store returns
weights_cap <- function(data,j){
# More general than before: we feed all the data, not just returns
m <- median(data$Mkt_Cap) # Compute the median market cap
n <- nrow(data) # Compute the number of assets
if(j == 1){return((data$Mkt_Cap < m)/n*2)} # Small cap
if(j == 2){return((data$Mkt_Cap > m)/n*2)} # Large cap
}
There will only be Tt-1 dates since we lose one because of the computation of future returns.
Second, we can launch the backtesting loop.
for(t in 2:length(t_oos)){
temp_data <- data %>% filter(Date == t_oos[t-1]) # We keep the data of the previous date
for(j in 1:nb_port){ # We loop on the strategies
portf_weights[t-1,j,] <- weights_cap(temp_data, j) # The weights' function is indexed by j
realised_returns <- returns %>%
filter(Date == t_oos[t]) %>% # Shift in the date
na.omit() %>%
select(-Date)
portf_returns[t-1,j] <- sum(portf_weights[t-1,j,] * realised_returns)
}
}
Third, we proceed to performance metrics.
apply(portf_returns, 2, perf_met) %>% # Taking perf metrics
unlist() %>% # Flattening the list
matrix(nrow = 2, byrow = T) %>% # Ordering them
`colnames<-`(c("avg_ret", "vol", "SR", "VaR")) %>% # Adding column names
data.frame() # Converting to dataframe
Small firms do indeed generate a higher level of performance! In order to reach this conclusion in a rigourous fashion, we would need to perform the same analysis on at least 1,000 stocks (ideally, more) and on 5 to 10 portfolio sorts (from very small firms to very large ones). Below, we check the weights of the portfolio on one particular date.
small <- portf_weights[2,1,] # t = 2, j = 1 (t_oos[2] = 2010-03-01, small firms)
large <- portf_weights[2,2,] # t = 2, j = 2 (t_oos[2] = 2010-03-01, large firms)
data.frame(small, large, row.names = tick)
Indeed, some stocks have zero weights and others 1/15.
Finally, letās see how we could have coded those strategies using the tidyverse (and a lot of piping!).
data %>% filter(Date > sep_date) %>% # Keep only the out-of-sample backtesting dates
group_by(Tick) %>% # Group by stock
mutate(F_Return = dplyr::lead(Return)) %>% # Compute forward (i.e., realised) return
na.omit() %>% # Take out NAs
group_by(Date) %>% # Group by dates
mutate(Mkt_Cap_Binary = Mkt_Cap < median(Mkt_Cap)) %>% # Compute median cap for each date
ungroup() %>%
group_by(Mkt_Cap_Binary) %>% # Group by Mkt_Cap: small vs large
summarise(avg_return = mean(F_Return)) # Simple pivot table
It can be useful to see how often stocks switch from one family to another (from below median to above median or vice-versa). Below, we show a plot of Mkt_Cap, conditional on Mkt_Cap being above the current median.
data %>% group_by(Date) %>% # Group by date
mutate(Mkt_Cap_median = median(Mkt_Cap)) %>% # Compute median cap for each date
filter(Mkt_Cap > Mkt_Cap_median) %>% # Keep only the large stocks
ggplot(aes(x = Date, y = Mkt_Cap, color = Tick)) + # Plot
geom_line() + ylim(75000,250000) +
geom_line(aes(x = Date, y = Mkt_Cap_median), color = "black")

# The black line shows the running median
The straight lines show the discontinuities: one stock being large at some point in time, then small and then large again. The straight lines show the periods when the stock was small. The black line shows the median capitalisation (in the sample). Finally, because we focus in the zone close to the median and impose an upper limit of 250B$, there are some missing points.
Sustainable investing
ESG investing has gained a lot of traction (see my review paper: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3715753). In this section, we briefly explore this topic.
First, a glance at the data. Letās look at the distribution of ESG_rank (from Sustainalytics).
load("data_esg.RData") # Loading the data
data_esg %>%
mutate(Year = year(Date)) %>%
ggplot(aes(x = ESG_rank, fill = as.factor(Year))) +
geom_histogram() + labs(fill = "Year") + theme_light()

There are few firms with extreme ESG_rank (below 10 or above 90).
Letās continue with a āsimpleā piping flow that creates a compact dataset.
data_esg2 <- data_esg %>%
select(Tick, Date, Close, ESG_rank) %>% # Keep relevant columns
filter(Date > "2014-02-01") %>% # Data available after 2014-02-01
group_by(Tick) %>%
mutate(Return = dplyr::lead(Close)/Close - 1) %>% # Forward return
ungroup() %>%
group_by(Date) %>% # For each date: create ESG groups
mutate(ESG_group = if_else(ESG_rank > median(ESG_rank), "High_ESG", "Low_ESG")) %>%
ungroup()
data_esg2
Based on this short dataset, letās have a quick look at the perf of the 2 groups (high ESG versus low ESG).
data_esg2 %>%
group_by(Date, ESG_group) %>%
summarise(Return = mean(Return, na.rm = T)) %>%
group_by(ESG_group) %>%
summarise(avg_return = mean(Return, na.rm = T), # Be careful with na.rm = T
vol = sd(Return, na.rm = T),
SR = avg_return/vol)
Two conclusions:
1. High ESG does slightly better.
2. But the difference is not huge (t-stat => exercise!)
From individual annual returns: is there are pattern?
data_esg2 %>%
mutate(Year = year(Date)) %>%
group_by(Year, Tick) %>%
summarise(avg_ESG = mean(ESG_rank, na.rm = T),
avg_return = mean(Return, na.rm = T)) %>%
ggplot(aes(x = avg_ESG, y = avg_return)) + geom_point(alpha = 0.3) +
geom_smooth(method = "lm") + theme_light()

No pattern at all, it seemsā¦
Letās dig deeper and have a look at screening/selection intensity. We compute the average returns of firms that have ESG_rank above a given threshold. To do that, letās make a function.
library(scales) # This will be used in the plot below to zoom on the values with special limits
ESG_impact <- function(level, data_esg2){
data_esg2 %>%
filter(ESG_rank > level) %>% # Filter to keep only the firms with ESG > level
pull(Return) %>%
mean(na.rm = T)
}
level_esg <- 10*(1:9) # ESG_rank threshold
map_dbl(level_esg, ESG_impact, data_esg2 = data_esg2) # The raw result
[1] 0.01106186 0.01111554 0.01128353 0.01122823 0.01153817 0.01141918 0.01184463 0.01164315 0.01184526
level_esg %>%
bind_cols(return = map_dbl(level_esg, ESG_impact, data_esg2 = data_esg2)) %>%
ggplot(aes(x = level_esg, y = return)) + geom_col(alpha = 0.5) +
theme_light() + scale_y_continuous(limits=c(0.008,0.012), oob = rescale_none)

Overall, higher ESG selection seems promising indeed (but letās not jump to general conclusions). Finally, letās have a look at more homogeneous groups. We need different reference points (level_esg) because of the distribution of ESG_rank.
ESG_quant <- function(level, width, data_esg2){ # A new function
data_esg2 %>%
filter(ESG_rank > level - width/2,
ESG_rank < level + width/2) %>% # Filter to keep firms with ESG around level
pull(Return) %>%
mean(na.rm = T)
}
level_esg <- quantile(data_esg$ESG_rank, seq(0.1,0.9, by = 0.1))
level_esg %>%
bind_cols(return = map_dbl(level_esg, ESG_quant, width = 10, data_esg2 = data_esg2)) %>%
ggplot(aes(x = level_esg, y = return)) + geom_col(alpha = 0.5) +
theme_light() + scale_y_continuous(limits=c(0.007,0.0125), oob = rescale_none)
New names:
* `` -> ...1

The effect is not monotonic: things are not that simpleā¦
Exercises
Rolling window
Change the main loop so that only 60 points of data are given to the weighting scheme(s). Sixty points amount to 5 years of monthly data.
Minimum variance
Add the MV portfolio to the set of strategies. The weights depend only on the covariance matrix: \(w=\frac{\Sigma^{-1}1}{1'\Sigma^{-1}1}\).
map() expertise
Extend the map() syntax to the case with many strategies. BONUS: have a look at pmap()!
Realistic portfolios
In practice, many saveguards are applied, if only to reduce turnover. One such example is box constraint: the weights in the portfolio must not lie above or below user-specified thresholds.
In minimum variance, it is possible to reduce leverage by shrinking the covariance matrix towards the identity functions: \[\Sigma^*=(1-\alpha) \Sigma^S+\alpha I,\] where \(\Sigma^S\) is the sample covariance matrix and \(I\) the identity matrix. As \(\alpha\) increases to 1, the weights converge to the equally-weighted portfolio.
LS0tCnRpdGxlOiAiUG9ydGZvbGlvIGJhc2ljcyIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKICAgIHRvY19mbG9hdDogCiAgICAgIGNvbGxhcHNlZDogZmFsc2UKLS0tCgpUaGlzIGlzIHRoZSBjb21wYW5pb24gbm90ZWJvb2sgdG8gdGhlIGludHJvZHVjdG9yeSBjb3Vyc2Ugb24gc2ltcGxlICoqcG9ydGZvbGlvIGNvbnN0cnVjdGlvbioqIGFuZCAqKnBlcmZvcm1hbmNlIG1ldHJpY3MqKi4gSXQgY29udGFpbnMgc2ltcGxlIGV4YW1wbGVzIG9mICoqcG9ydGZvbGlvIGJhY2t0ZXN0aW5nKiouIFRoZSBzdHJ1Y3R1cmVzIG9mIHRoaXMgc2VjdGlvbiB3aWxsIGJlIHVzZWQgbGF0ZXIgb24gaW4gdGhlIGNvdXJzZS4KCiRccmlnaHRhcnJvdyQgKipBQk9VVCBUSEUgTk9URUJPT0sqKjogICAKCi0gdGhlIGNvZGUgY2h1bmtzIGFyZSAqKnNlcXVlbnRpYWwqKi4gVGhleSBtdXN0IGJlIGV4ZWN1dGVkIGluIHRoZSBjb3JyZWN0IG9yZGVyLiAgCi0gdGV4dCBiZXR3ZWVuICoqc3RhcnMqKiBhcHBlYXJzIGluIGJvbGQgaW4gaHRtbCBmb3JtYXQuICAKCiMgQSBnbGltcHNlIGF0IHRoZSBTJlA1MDAKVGhlICoqUyZQNTAwKiogaXMgb25lIG9mIHRoZSBtb3N0IHdpZGVseSBzY3J1dGluaXNlZCBpbmRleCBpbiB0aGUgVVMgRXF1aXR5IGludmVzdG1lbnQgc3BhY2UuIEl0IHNlcnZlcyB2ZXJ5IG9mdGVuIGFzICoqYmVuY2htYXJrKiouIFRoZSBwdXJwb3NlIG9mIHRoaXMgc2VjdGlvbiBpcyB0byB1bnZlaWwgYSBmZXcgb2YgaXRzIHN0YXRpc3RpY2FsIHByb3BlcnRpZXMgYW5kIHRvIHVzZSB0aGUgKipoaWdoY2hhcnRlcioqIHBhY2thZ2UgZm9yIGhpZ2hjaGFydCByZW5kZXJpbmcgaW4gUi4KCiMjIFByaWNlcwpXZSBzdGFydCBieSBsb2FkaW5nIHRoZSBwYWNrYWdlcyBhbmQgZG93bmxvYWRpbmcgdGhlIGRhdGEuIEZvciB0ZWNobmljYWwgcmVhc29ucywgd2UgZG93bmxvYWQgdGhlIHNlcmllcyBvZiB0aGUgRVRGIHJlcGxpY2F0aW5nIHRoZSBTJlA1MDAgKFNQWSB0aWNrZXIpLgoKYGBge3IgbG9hZF9zMiwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CmlmKCFyZXF1aXJlKGhpZ2hjaGFydGVyKSl7aW5zdGFsbC5wYWNrYWdlcygiaGlnaGNoYXJ0ZXIiKX0gIyBQYWNrYWdlIGZvciBuaWNlIGZpbmFuY2lhbCBncmFwaHMKaWYoIXJlcXVpcmUoc2NhbGVzKSl7aW5zdGFsbC5wYWNrYWdlcygic2NhbGVzIil9ICAgICAgICAgICAjIFBhY2thZ2UgZm9yIGdyYXBoIHNjYWxlcwpsaWJyYXJ5KHRpZHl2ZXJzZSkgICAjIFRoZSBkYXRhIHdyYW5nbGluZyBwYWNrYWdlCmxpYnJhcnkocGxvdGx5KSAgICAgICMgRm9yIGludGVyYWN0aXZlIGdyYXBocwpsaWJyYXJ5KGx1YnJpZGF0ZSkgICAjIEZvciBkYXRhIG1hbmFnZW1lbnQKbGlicmFyeShxdWFudG1vZCkgICAgIyBUaGUgcGFja2FnZSB0aGF0IGVhc2VzIHRoZSBkb3dubG9hZGluZyBvZiBmaW5hbmNpYWwgZGF0YQpsaWJyYXJ5KGhpZ2hjaGFydGVyKSAjIFRoZSBwYWNrYWdlIGZvciBmaW5hbmNpYWwgdGltZS1zZXJpZXMgcGxvdHMKCm1pbl9kYXRlIDwtICIxOTgwLTAxLTAxIgptYXhfZGF0ZSA8LSAiMjAyMS0wNS0wNSIKcHJpY2VzIDwtIGdldFN5bWJvbHMoIlNQWSIsIHNyYyA9ICd5YWhvbycsICAjIFlhaG9vIHNvdXJjZSAoRVRGIHRpY2tlcikgXkdTUEMKICAgICAgICAgICAgICAgICAgICAgZnJvbSA9IG1pbl9kYXRlLCAKICAgICAgICAgICAgICAgICAgICAgdG8gPSBtYXhfZGF0ZSwKICAgICAgICAgICAgICAgICAgICAgYXV0by5hc3NpZ24gPSBUUlVFLCAKICAgICAgICAgICAgICAgICAgICAgd2FybmluZ3MgPSBGQUxTRSkgJT4lCiAgbWFwKH5BZChnZXQoLikpKSAlPiUgCiAgcmVkdWNlKG1lcmdlKSAlPiUKICBgY29sbmFtZXM8LWAoIlNQWSIpCmBgYAoKClRoZW4sIHdlIHR1cm4gdG8gcGxvdHRpbmcsIHVzaW5nICoqaGlnaGNoYXJ0KiogZm9ybWF0LiBXZSB1bmRlcmxpbmUgdGhhdCB0aGlzIHBhY2thZ2Ugd29ya3Mgd2l0aCBzcGVjaWFsICoqeHRzKiogKFIgZXh0ZW5zaWJsZSB0aW1lLXNlcmllcykgZm9ybWF0LiBXZSBwb2ludCB0byB0aGUgcGFja2FnZSByZWZlcmVuY2UgZm9yIG1vcmUgZGV0YWlscyBvbiB0aGlzIHN1YmplY3Q6ICAgCi0gaHR0cHM6Ly9qa3Vuc3QuY29tL2hpZ2hjaGFydGVyLyAgIAotIGh0dHBzOi8vd3d3LmhpZ2hjaGFydHMuY29tL2Jsb2cvdHV0b3JpYWxzL2hpZ2hjaGFydHMtZm9yLXItdXNlcnMvICAgCi0gaHR0cHM6Ly9jcmFuLnItcHJvamVjdC5vcmcvd2ViL3BhY2thZ2VzL2hpZ2hjaGFydGVyL2luZGV4Lmh0bWwKCgpgYGB7ciBoaWdoY2hhcnRfc3RvY2ssIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpoaWdoY2hhcnQodHlwZSA9ICJzdG9jayIpICU+JQogIGhjX3RpdGxlKHRleHQgPSAiRXZvbHV0aW9uIG9mIHRoZSBTUFkiKSAlPiUKICBoY19hZGRfc2VyaWVzKHByaWNlcykKYGBgCgoKQSBuaWNlIGZlYXR1cmUgb2YgaGlnaGNoYXJ0cyBpcyB0aGF0IHRoZXkgYWxsb3cgdGhlIHVzZXIgdG8gKipjaGFuZ2UgdGhlIG9ic2VydmF0aW9uIHBlcmlvZCoqIGFuZCBzZWUgdGhlIHZhbHVlcyBvZiBwb2ludHMgb24gdGhlIGN1cnZlLiAKCiMjIFJldHVybnMKTmV4dCwgd2UgdHVybiB0byB0aGUgZGlzdHJpYnV0aW9uIG9mIHJldHVybnMuCgpgYGB7ciByZXRfZGVmLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KcmV0dXJucyA8LSBwcmljZXMgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAjIEZvcm11bGEgZm9yIHJldHVybnMKICBkYXRhLmZyYW1lKERhdGUgPSBpbmRleCguKSkgJT4lICAgICAgICAgICAgICAjIEFkZGluZyB0aGUgRGF0ZSBhcyBhIGNvbHVtbgogIG11dGF0ZShTUFkgPSBTUFkgLyBkcGx5cjo6bGFnKFNQWSkgLSAxKSAlPiUgICMgUmV0dXJucwogIG5hLm9taXQoKSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgUmVtb3ZpbmcgTkEgcm93cwptIDwtIG1lYW4ocmV0dXJucyRTUFkpICAgICAgICAgICAgICAgICAgICAgICAgICMgQXZlcmFnZSBkYWlseSByZXR1cm4KcyA8LSBzZChyZXR1cm5zJFNQWSkgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFZvbGF0aWxpdHkgPSBzZCBvZiBkYWlseSByZXR1cm5zCgpyZXR1cm5zICU+JSBnZ3Bsb3QoKSArICAgICAgICAgICAgICAgICAgICAgICAgICMgUGxvdAogIGdlb21faGlzdG9ncmFtKGFlcyh4ID0gU1BZLCB5ID0gLi5kZW5zaXR5Li4pLCBiaW5zID0gMTAwLCBhbHBoYSA9IDAuNikgKyB0aGVtZV9saWdodCgpICsKICBzdGF0X2Z1bmN0aW9uKGZ1biA9IGRub3JtLCBhcmdzID0gbGlzdChtZWFuID0gbSwgc2QgPSBzKSwgYWVzKGNvbG9yID0gIkdhdXNzaWFuIikpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSBjKDAuNywgMC43KSkKYGBgCgpXZSBwbG90IHRoZSAqKkdhdXNzaWFuIGRlbnNpdHkqKiB3aXRoIHBhcmFtZXRlcnMgY29ycmVzcG9uZGluZyB0byB0aGUgc2FtcGxlIG1lYW4gYW5kIHN0YW5kYXJkIGRldmlhdGlvbi4gU21hbGwgZ3JleSByZWN0YW5nbGVzIGFyb3VuZCAkXHBtIDAuMDUkIGluZGljYXRlIHRoYXQgbGFyZ2UgcG9zaXRpdmUgYW5kIG5lZ2F0aXZlIHJldHVybnMgb2NjdXIgbW9yZSBvZnRlbiB0aGFuIGVzdGltYXRlIGJ5IHRoZSBHYXVzc2lhbiBsYXc6IHRoZSB0YWlscyBvZiB0aGVpciBkaXN0cmlidXRpb24gYXJlIG5vdG9yaW91c2x5ICoqaGVhdnkqKi4KCiMjIFZvbGF0aWxpdHkKRmluYWxseSwgd2UgdGFrZSBhIGR5bmFtaWMgbG9vayBhdCB0aGUgdm9sYXRpbGl0eS4gV2UgdGFrZSBhIGZydWdhbCBhcHByb2FjaDsgbXVjaCBtb3JlIGVsZWdhbnQgbWV0aG9kcyBhcmUgcHJlc2VudGVkIGluIFNlY3Rpb24gNC41IG9mICoqUmVwcm9kdWNpYmxlIEZpbmFuY2UqKiBieSBKb25hdGhhbiBSZWdlbnN0ZWluLCBhcyB3ZWxsIGFzIHRoZSByb2xsX3NkKCkgZnVuY3Rpb24gdXNlZCBpbiBodHRwOi8vd3d3LnJlcHJvZHVjaWJsZWZpbmFuY2UuY29tL2RyYWZ0cy9wb3N0L3ZpeC1hbmQtcmVhbGl6ZWQtdm9sYXRpbGl0eS11cGRhdGluZy1vdXItcHJldmlvdXMtd29yay8KCmBgYHtyIHZvbCwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9Cm5iX2RheXMgPC0gNjMgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIDYzIGRheXMgcm91Z2hseSBlcXVpdmFsZW50IHRvIDMgbW9udGhzIAp2b2wgPC0gMCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBJbml0aWFsaXNhdGlvbgpmb3IoaSBpbiAxOihucm93KHJldHVybnMpIC0gbmJfZGF5cyArIDEpKXsgICAgICAgICAgIyBMb29wIG9uIGRhdGVzOiBub3QgZWxlZ2FudCEKICB2b2xbaV0gPC0gc2QocmV0dXJucyRTUFlbaTooaSArIG5iX2RheXMgLSAxKV0pICAgICMgRm9yd2FyZCB2b2wgY29tcHV0ZWQgb24gcm9sbGluZyB3aW5kb3cgb2YgbmJfZGF5cwp9CkRhdGUgPC0gcmV0dXJucyREYXRlW25iX2RheXM6bnJvdyhyZXR1cm5zKV0gICAgICAgICAjIFZlY3RvciBvZiBkYXRlcwp2b2wgPC0gZGF0YS5mcmFtZSh2b2wqc3FydCgyNTIpKSAgICAgICAgICAgICAgICAgICAgIyBWZWN0b3IgaW5zaWRlIGEgZGF0YWZyYW1lCgpyb3duYW1lcyh2b2wpIDwtIERhdGUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBDaGFuZ2UgdGhlIGluZGV4IG9mIHRoZSBkYXRhZnJhbWUKaGlnaGNoYXJ0KHR5cGUgPSAic3RvY2siKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICMgQ29kZSBmb3IgdGhlIHBsb3QKICBoY190aXRsZSh0ZXh0ID0gIkV2b2x1dGlvbiBvZiByZWFsaXplZCB2b2xhdGlsaXR5IikgJT4lCiAgaGNfYWRkX3Nlcmllcyhhcy54dHModm9sKSkKYGBgCgpDbGVhcmx5IHRoZSBncmFwaCBzaG93cyBwZXJpb2RzIG9mIGxvdyB2b2xhdGlsaXR5IGFuZCAqKmNsdXN0ZXJzKiogb2YgaGlnaCBtYXJrZXQgdHVyYnVsZW5jZSAoY3Jhc2hlcywgbW9zdCBvZiB0aGUgdGltZSkuIFJldHVybnMgYXJlIHRoZXJlZm9yZSAqKm5vdCBzdGF0aW9uYXJ5KiouIFRoZSBwcm9wZXJ0aWVzIHdlIGV4aGliaXRlZCBmb3IgdGhlIFMmUDUwMCBhcmUgYWxzbyB0cnVlIGF0IHRoZSBpbmRpdmlkdWFsIHN0b2NrIGxldmVsLgoKSW4gdGhlIG5leHQgc2VjdGlvbnMsIHdlIHR1cm4gdG8gdGhlIGNvcmUgdG9waWMgb2YgKipwb3J0Zm9saW8gYmFja3Rlc3RpbmcqKi4KCiMgRGF0YQoKRmlyc3QsIGxldCdzIHN0YXJ0IHdpdGggdGhlIHByZXByb2Nlc3Npbmcgb2YgdGhlIGRhdGEuCgpXZSBmaXJzdCBpbXBvcnQgYW5kIGFycmFuZ2UgdGhlIGRhdGEuIApUaGUgZGF0YSBjb25zaXN0cyBvZiBtb25odGx5IGZpbmFuY2lhbCBpbmZvcm1hdGlvbiBwZXJ0YWluaW5nIHRvIDMwIGxhcmdlIFVTIGZpcm1zLiBUaGV5IGFyZSBjaGFyYWN0ZXJpc2VkIGJ5IHRoZWlyICoqdGlja2VyKiogc3ltYm9sOiAgCgp8QSAtIEZ8IEcgLSBNIHxPIC0gWnwKfCAtLS0gfCAtLS0tLSB8IC0tLSB8CnwgQUFQTCAoQXBwbGUpfCBHRSAoR2VuZXJhbCBFbGVjdHJpYykgfCBPUkNMIChPcmFjbGUpCnwgQkEgKEJvZWluZykgfCBIRCAoSG9tZSBEZXBvdCkgfCBQRkUgKFBmaXplcikKfCBCQUMgKEJhbmsgb2YgQW1lcmljYSkgfCBJQk0gfCBQRyAoUHJvY3RlciAmIEdhbWJsZSkKfCBDIChDaXRpZ3JvdXApIHwgSU5UQyAoSW50ZWwpIHwgVCAoQVQmVCkKfENTQ08gKENpc2NvKSB8IEpOSiAoSm9obnNvbiAmIEpvaG5zb24pIHwgIFVOSCAoVW5pdGVkIEhlYWx0aCkKfENWUyAoQ1ZTIEhlYWx0aCkgfCBKUE0gKEpQIE1vcmdhbikgfCBVUFMgCnxDVlggKENoZXZyb24pIHwgSyAoS2VsbG9nZykgfCBWWiAoVmVyaXpvbikKfEQgKERvbWluaW9uIEVuZXJneSkgfCBNQ0sgKE1jS2Vzc29uKSB8IFdGQyAoV2VsbHMgRmFyZ28pCnxESVMgKERpc25leSkgfCBNUksgKE1lcmNrKSB8IFdNVCAoV2FsbWFydCkKfEYgKEZvcmQpIHwgTVNGVCAoTWljcm9zb2Z0KSB8IFhPTSAoRXh4b24pCgoKVGhlcmUgYXJlIDcgYXR0cmlidXRlczogY2xvc2luZyBwcmljZSAoKipDbG9zZSoqKSwgbWFya2V0IGNhcGl0YWxpc2F0aW9uIGluIE0kICgqKk1rdF9DYXAqKiksIHByaWNlLXRvLWJvb2sgcmF0aW8gKCoqUDJCKiopLCAxIG1vbnRoIHZvbGF0aWxpdHkgKCoqVm9sXzFNKiopLCAxIG1vbnRoIHJlbGF0aXZlIHN0cmVuZ3RoIGluZGV4ICgqKlJTSV8xTSoqKSwgZGVidC10by1lcXVpdHkgcmF0aW8gKCoqRDJFKiopIGFuZCBwcm9maXRhYmlsaXR5IG1hcmdpbiAoKipQcm9mX01hcmcqKikuICAgCkZpbmFsbHksIHRoZSB0aW1lIHJhbmdlIGlzIDIwMDAtMjAyMS4KCmBgYHtyIGluaXRpYXRlLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KbG9hZCgiZGF0YS5SRGF0YSIpICAgICAgICAgICAgICAgICAgICAgICMgTG9hZGluZyB0aGUgZGF0YTogSUYgRElSRUNUT1JZIE9LIQpkYXRhIDwtIGRhdGEgJT4lIGFycmFuZ2UoRGF0ZSxUaWNrKSAgICAgIyBSYW5rZWQgZmlyc3QgYWNjb3JkaW5nIHRvIGRhdGUgYW5kIHRoZW4gc3RvY2tzCnN1bW1hcnkoZGF0YSkgICAgICAgICAgICAgICAgICAgICAgICAgICAjIERlc2NyaXB0aXZlIHN0YXRpc3RpY3MKdGljayA8LSB1bmlxdWUoZGF0YSRUaWNrKSAgICAgICAgICAgICAgICMgU2V0IG9mIGFzc2V0cwp0X2FsbCA8LSB1bmlxdWUoZGF0YSREYXRlKSAgICAgICAgICAgICAgIyBTZXQgb2YgZGF0ZXMKTiA8LSBuX2Rpc3RpbmN0KGRhdGEkVGljaykgICAgICAgICAgICAgICMgTnVtYmVyIG9mIHN0b2NrcwpgYGAKClRoaXMgc2ltcGxlIHRhYmxlIHNob3dzIGEgcG9zc2libGUgb3V0bGllciBmb3IgdGhlICoqUDJCKiogdmFyaWFibGUuIFRoZSBtYXhpbXVtIHZhbHVlIGlzIGNsZWFybHkgb3V0IG9mIHJhbmdlLiAgCgpOZXh0LCB3ZSBmb3JtYXQgdGhlIGRhdGEgZm9yIGZ1dHVyZSB1c2UuIE5vdGFibHksIHdlIGNvbXB1dGUgJiBzdG9yZSByZXR1cm5zLgoKYGBge3J9CmRhdGEgPC0gZGF0YSAlPiUgCiAgZ3JvdXBfYnkoVGljaykgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEdyb3VwaW5nOiByZXR1cm5zIGNvbXB1dGVkIHN0b2NrLWJ5LXN0b2NrCiAgbXV0YXRlKFJldHVybiA9IENsb3NlIC8gZHBseXI6OmxhZyhDbG9zZSkgLSAxKSAlPiUgICAjIEFkZGluZyByZXR1cm5zCiAgdW5ncm91cCgpCgpyZXR1cm5zIDwtIGRhdGEgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBUYWtlIGRhdGEKICBzZWxlY3QoVGljaywgRGF0ZSwgUmV0dXJuKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICMgU2VsZWN0IDMgY29sdW1ucwogIHBpdm90X3dpZGVyKG5hbWVzX2Zyb20gPSBUaWNrLCB2YWx1ZXNfZnJvbSA9IFJldHVybikgIyBQdXQgdGhlbSBpbnRvICdtYXRyaXgnIGZvcm1hdApyZXR1cm5zICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBTaG93IHRoZSByZXR1cm5zCmBgYAoKCiMgV2hhdCBzdHVkZW50cyBvZnRlbiBkby4uLgoKTm93LCBsZXQncyBjb25zaWRlciB0aGUgdXN1YWwgTWFya293aXR6IGFsbG9jYXRpb24gc3ViamVjdCB0byB0aGUgYnVkZ2V0IGNvbnN0cmFpbnQgJFx0ZXh0YmZ7d30nXHRleHRiZnsxfT0xJDoKCiQkXHRleHR7bWF4fSBcIFx0ZXh0YmZ7d30nXGJvbGRzeW1ib2x7XG11fSAtIFxmcmFje1xnYW1tYX17Mn1cdGV4dGJme3d9J1xib2xkc3ltYm9se1xTaWdtYX1cdGV4dGJme3d9LCBccXVhZCBcdGV4dHtzLnQufSBccXVhZCBcdGV4dGJme3d9J1x0ZXh0YmZ7MX09MSAkJAp3aXRoIExhZ3JhbmdpYW46CiQkTChcdGV4dGJme3d9KT1cdGV4dGJme3d9J1xib2xkc3ltYm9se1xtdX0gLSBcZnJhY3tcZ2FtbWF9ezJ9XHRleHRiZnt3fSdcYm9sZHN5bWJvbHtcU2lnbWF9XHRleHRiZnt3fStcZGVsdGEgKFx0ZXh0YmZ7d30nXHRleHRiZnsxfS0xKSQkCnNvIHRoYXQgCiQkXGZyYWN7XHBhcnRpYWwgTH17XHBhcnRpYWwgXHRleHRiZnt3fX09XGJvbGRzeW1ib2x7XG11fS1cZ2FtbWFcYm9sZHN5bWJvbHtcU2lnbWF9XHRleHRiZnt3fStcZGVsdGFcdGV4dGJmezF9PTAgXHF1YWQgXFJpZ2h0YXJyb3cgXHF1YWQgXHRleHRiZnt3fT1cZ2FtbWFeey0xfVxib2xkc3ltYm9se1xTaWdtYX1eey0xfShcYm9sZHN5bWJvbHtcbXV9K1xkZWx0YSBcdGV4dGJmezF9KSwkJAp3aGVyZSAkXGRlbHRhJCBpcyBjaG9zZW4gdG8gc2F0aXNmeSB0aGUgYnVkZ2V0IGNvbnN0cmFpbnQuIEEgcGFydGljdWxhciBjYXNlIGlzIHRoZSBtaW5pbXVtIHZhcmlhbmNlIHBvcnRmb2xpbyB3aGljaCBjb3JyZXNwb25kcyB0byAkXGJvbGRzeW1ib2x7XG11fT1cdGV4dGJmezF9JDogdGhlIG9wdGltYWwgcG9ydGZvbGlvIGlzIHByb3BvcnRpb25hbCB0byAkXGJvbGRzeW1ib2x7XFNpZ21hfV57LTF9IFx0ZXh0YmZ7MX0kLgoKYGBge3Igc3RhdGljLCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9ClNpZ21hIDwtIHJldHVybnMgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBDb3ZhcmlhbmNlIG1hdHJpeAogIHNlbGVjdCgtRGF0ZSkgJT4lIAogIGNvdih1c2UgPSAiY29tcGxldGUub2JzIikKU2lnbWFbMTo5LDE6OV0gJT4lIHJvdW5kKDMpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEEgcXVpY2sgbG9vayBhdCBTaWdtYQpNaW5fdmFyX3dlaWdodHMgPC0gc29sdmUoU2lnbWEpICUqJSByZXAoMSxOKSAgICAgICAgICAgICAgICMgUHJvcG9ydGlvbmFsIHdlaWdodHMKTWluX3Zhcl93ZWlnaHRzIDwtIE1pbl92YXJfd2VpZ2h0cyAvIHN1bShNaW5fdmFyX3dlaWdodHMpICAjIEV4YWN0IChzY2FsZWQpIHdlaWdodHMKYmluZF9jb2xzKHRpY2ssIE1pbl92YXJfd2VpZ2h0cykgJT4lCiAgZ2dwbG90KGFlcyh4ID0gTWluX3Zhcl93ZWlnaHRzLCB5ID0gdGljaykpICsgICAgICAgICAgICAgIyBQbG90CiAgZ2VvbV9jb2woYWxwaGEgPSAwLjUpICsgdGhlbWVfbGlnaHQoKQpgYGAKCk5hdHVyYWxseSwgdGhlIHN0b2NrcyB3aXRoIHN1cGVyIGxvdyB2b2xhdGlsaXR5IChEaXNuZXksIFdhbG1hcnQpIGFyZSBmYXZvcmVkIQpMZXQncyBzZWUgd2hlbiB0aGUgd2VpZ2h0cyBhcmUgZHJpdmVuIGJ5IHRoZSBtZWFuIHJldHVybnMuLi4KCmBgYHtyLCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9Cm11IDwtIHJldHVybnMgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBNZWFuIHZlY3RvciAKICBzZWxlY3QoLURhdGUpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFJlbW92ZSBkYXRlCiAgY29sTWVhbnMobmEucm0gPSBUKQpNYXJrb193ZWlnaHRzIDwtIHNvbHZlKFNpZ21hKSAlKiUgbXUgICAgICAgICAgICAgICAgICMgUHJvcG9ydGlvbmFsIHdlaWdodHMKTWFya29fd2VpZ2h0cyA8LSBNYXJrb193ZWlnaHRzIC8gc3VtKE1hcmtvX3dlaWdodHMpICAjIEV4YWN0IChzY2FsZWQpIHdlaWdodHMKYmluZF9jb2xzKHRpY2ssIE1hcmtvX3dlaWdodHMpICU+JQogIGdncGxvdChhZXMoeCA9IE1hcmtvX3dlaWdodHMsIHkgPSB0aWNrKSkgKyAgICAgICAgICMgUGxvdAogIGdlb21fY29sKGFscGhhID0gMC41KSArIHRoZW1lX2xpZ2h0KCkKYGBgCgoqQUFQTCogYW5kICpVTkgqIGhhdmUgaGlnaCByZXR1cm5zID0+IGhpZ2ggd2VpZ2h0cy4KCk5vdyBsZXQncyBsb29rIGF0IDIgd2F5cyBvZiBwcm9jZXNzaW5nIHRoZXNlIHdlaWdodHMgaW50byBwb3J0Zm9saW8gdmFsdWVzLgoKYGBge3IgdWdseV93YXksIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0Kd19tYXRyaXggPC0gbWF0cml4KE1hcmtvX3dlaWdodHMsIAogICAgICAgICAgICAgICAgICAgbmNvbCA9IE4sIG5yb3cgPSBsZW5ndGgodF9hbGwpIC0gMSwgYnlyb3cgPSBUKSAjIFdlaWdodCBtYXRyaXgKKHJvd1N1bXMoKHJldHVybnMgJT4lIHNlbGVjdCgtRGF0ZSkpICogd19tYXRyaXgpICsgMSkgJT4lICAgICAgICAgIyBTaW1wbGUgcHJvZHVjdCA9IGVsZW1lbnQtd2lzZQogIG5hLm9taXQoKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFJlbW92ZSBtaXNzaW5nIHBvaW50cwogIGN1bXByb2QoKSAlPiUgcm91bmQoMykgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEN1bXVsYXRpdmUgcHJvZHVjdCArIHJvdW5kaW5nCmBgYAoKVGhlIGFib3ZlIGNvZGUgaXMgdWdseS4gQmVjYXVzZSB0aGUgZGF0YSBpcyBuZWF0bHkgb3JkZXJlZCwgd2UgY2FuIGRvIGJldHRlciEKTGV0J3MgYWRkIGEgbmV3IGNvbHVtbiB0byB0aGUgZGF0YS4KCmBgYHtyfQpkYXRhICU+JSAKICBzZWxlY3QoVGljaywgRGF0ZSwgUmV0dXJuKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICMgS2VlcCBvbmx5IG5lY2Vzc2FyeSBjb2xzCiAgYmluZF9jb2xzKHdfTWFya28gPSByZXAoTWFya29fd2VpZ2h0cywgbGVuZ3RoKHRfYWxsKSkpICAjIEJpbmQgY29sczogYmV3YXJlIHRvIHRoZSBvcmRlciEKYGBgCgpOb3cgd2UgY2FuIGFkZCBiZW5jaG1hcmsgd2VpZ2h0cyBhbmQgcHJvY2VlZC4KCmBgYHtyLCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9CnAgPC0gZGF0YSAlPiUgCiAgc2VsZWN0KFRpY2ssIERhdGUsIFJldHVybikgJT4lCiAgYmluZF9jb2xzKHdfTWFya28gPSByZXAoTWFya29fd2VpZ2h0cywgbGVuZ3RoKHRfYWxsKSkpICU+JQogIG11dGF0ZSh3X2JlbmNobWFyayA9IDEvMzApICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBBZGQgYmVuY2htYXJrIHdlaWdodHMgMS9OCiAgcGl2b3RfbG9uZ2VyKGNvbHMgPSBjKHdfTWFya28sIHdfYmVuY2htYXJrKSwgICAgICAgICAgICAgICAjIFBpdm90IHRvIHRpZHkKICAgICAgICAgICAgICAgbmFtZXNfdG8gPSAiUG9ydGZvbGlvIiwgIAogICAgICAgICAgICAgICB2YWx1ZXNfdG8gPSAiV2VpZ2h0IikgJT4lCiAgZ3JvdXBfYnkoRGF0ZSwgUG9ydGZvbGlvKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEdyb3VwIHRvIGNvbXB1dGUgcG9ydGYgcmV0dXJuCiAgc3VtbWFyaXNlKFJldHVybiA9IHN1bShXZWlnaHQgKiBSZXR1cm4pKSAlPiUgICAgICAgICAgICAgICAjIFBvcnRmIHJldHVybiwgZGF0ZS1ieS1kYXRlCiAgdW5ncm91cCgpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFVuZ3JvdXAKICBuYS5vbWl0KCkgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgUmVtb3ZlIG91dGxpZXJzCiAgZ3JvdXBfYnkoUG9ydGZvbGlvKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEdyb3VwIGFsb25nIHRoZSAyIHBvcnRmb2xpb3MKICBtdXRhdGUoVmFsdWUgPSBjdW1wcm9kKDErUmV0dXJuKSkgJT4lICAgICAgICAgICAgICAgICAgICAgICMgQ29tcHV0ZSBwb3J0Zm9saW8gdmFsdWVzCiAgZ2dwbG90KGFlcyh4ID0gRGF0ZSwgeSA9IFZhbHVlLCBjb2xvciA9IFBvcnRmb2xpbykpICsgICAgICAjIFBsb3QKICBnZW9tX2xpbmUoKSArIHRoZW1lX2xpZ2h0KCkgKyBzY2FsZV95X2xvZzEwKCkgKwogIHNjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXMgPSBjKCIjNzA2QzY2IiwgIiMwQTVCOTAiKSwgbGFiZWxzID0gYygiQmVuY2htYXJrIiwgIk1hcmtvd2l0eiIpKSArIAogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9IGMoMC4zLDAuNykpCgpnZ3Bsb3RseShwLCB3aWR0aCA9IDkwMCkKYGBgCgoKR2l2ZW4gdGhlIGxvZy1zY2FsZTogaXMgdGhpcyByZWFzb25hYmx5ICpyZWFsaXN0aWMqPwpPYnZpb3VzIGFuc3dlcjogKipOTyoqISBUaGUgd2VpZ2h0cyBoYXZlIGJlZW4gY2hvc2VuIHdpdGgga25vd2xlZGdlIG9mIHRoZSB0cmFqZWN0b3J5ISEhCkFsc286IHBvcnRmb2xpbyBtYW5hZ2VycyB1cGRhdGUgdGhlIHdlaWdodHMuLi4KCiMgQSB1bml2ZXJzZSBvZiBmdW5jdGlvbnMKCkJhY2t0ZXN0aW5nIHBvcnRmb2xpbyBzdHJhdGVnaWVzIGlzIHVzdWFsbHkgc2ltcGxlIGF0IGZpcnN0LCBidXQgYmVjb21lcyBtb3JlIGludHJpY2F0ZSB3aGVuIG1hbnkgb3B0aW9ucyBhcmUgY29uc2lkZXJlZC4gVG8ga2VlcCB0aGluZ3Mgc2ltcGxlLCBpdCBpcyBtb3JlIGVmZmljaWVudCB0byB3b3JrIHdpdGggZnVuY3Rpb25zLiAqKkZ1bmN0aW9ucyBoZWxwIGNvbXBhcnRtZW50YWxpc2UgdGhlIGRpZmZlcmVudCB0YXNrcyBvZiB0aGUgcHJvY2VzcyoqLiBXZSB3aWxsIGJ1aWxkIGZ1bmN0aW9ucyB0aGF0IGNvbXB1dGUgcG9ydGZvbGlvIHdlaWdodHMgYW5kIG90aGVycyB0aGF0IGV2YWx1YXRlIHRoZSBwZXJmb3JtYW5jZSBtZXRyaWNzIG9mIHRoZSBzdHJhdGVnaWVzLiBXaGlsZSB3ZSB3aWxsIHVzdWFsbHkgd29yayB3aXRoIGEgbG9vcCBvbiBiYWNrdGVzdGluZyBkYXRlcywgaXQgaXMgcG9zc2libGUgdG8gYnVpbGQgZnVuY3Rpb25zIHRoYXQgZGlyZWN0bHkgZ2VuZXJhdGUgcG9ydGZvbGlvIHJldHVybnMgKHNlZSBiZWxvdzogdGhlIG1hcCgpIGZ1bmN0aW9uKS4KCgpCeSBkZWZpbml0aW9uLCBhIHBvcnRmb2xpbyBpcyBhIGNob2ljZSBvZiB3ZWlnaHRzIHRoYXQgc3VtIHRvIG9uZS4gQmVsb3csIHdlIGltcGxlbWVudCB0d28gY2xhc3NpY2FsIHdlaWdodGluZyBzY2hlbWVzOiB0aGUgdW5pZm9ybSBwb3J0Zm9saW8gKCoqRVcqKiA9IGVxdWFsIHdlaWdodHMpIGFuZCB0aGUgbWF4aW11bSBTaGFycGUgcmF0aW8gcG9ydGZvbGlvICgqKk1TUioqKS4gVGhlIGxhdHRlciBpcyBtb3JlIGNvbXBsaWNhdGVkIGFuZCByZXF1aXJlcyBpbnB1dHM6IG5hbWVseSB0aGUgY29sdW1uIHZlY3RvciBvZiAoZXhwZWN0ZWQpIG1lYW4gJFxtdSQgYW5kIGNvdmFyaWFuY2UgbWF0cml4ICRcU2lnbWEkIG9mIHRoZSBhc3NldHMuIEZvciBzaW1wbGljaXR5LCB3ZSB3aWxsIGVzdGltYXRlIHRoZW0gdXNpbmcgKipzYW1wbGUgbW9tZW50cyoqIC0gZXZlbiB0aG91Z2ggdGhpcyBpcyBrbm93biB0byBiZSBhIGJhZCBjaG9pY2UuIFRoaXMgcmVxdWlyZXMgYW4gYWRkaXRpb25hbCBhcmd1bWVudCBpbiB0aGUgZnVuY3Rpb246IHRoZSBhc3NldHMnIHBhc3QgcmV0dXJucy4gVGhlICoqTVNSKiogd2VpZ2h0cyBhcmUgJHc9XGZyYWN7XFNpZ21hXnstMX1cbXV9ezEnXFNpZ21hXnstMX1cbXV9JC4gQm90aCAkXG11JCBhbmQgMSBhcmUgdmVjdG9ycyBoZXJlLgoKYGBge3Igd2VpZ2h0cywgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CndlaWdodHNfbXNyIDwtIGZ1bmN0aW9uKHJldHVybnMpeyAgIyByZXR1cm5zIHdpbGwgcmVmZXIgdG8gUEFTVCByZXR1cm5zCiAgbSA8LSBhcHBseShyZXR1cm5zLCAyLCBtZWFuKSAgICAgIyBWZWN0b3Igb2YgYXZlcmFnZSByZXR1cm5zCiAgc2lnbWEgPC0gY292KHJldHVybnMpICAgICAgICAgICAgIyBDb3ZhcmlhbmNlIG1hdHJpeAogIHcgPC0gc29sdmUoc2lnbWEpICUqJSBtICAgICAgICAgICMgUmF3IHdlaWdodHMKICByZXR1cm4odyAvIHN1bSh3KSkgICAgICAgICAgICAgICAjIFJldHVybnMgbm9ybWFsaXNlZCB3ZWlnaHRzCn0KCndlaWdodHNfZXcgPC0gZnVuY3Rpb24ocmV0dXJucyl7ICAgIyBXZSBrZWVwIHRoZSBzYW1lIHN5bnRheCBmb3Igc2ltcGxpY2l0eQogIE4gPC0gbGVuZ3RoKHJldHVybnNbMSxdKSAgICAgICAgICMgTnVtYmVyIG9mIGFzc2V0cwogIHJldHVybihyZXAoMS9OLE4pKSAgICAgICAgICAgICAgICMgV2VpZ2h0ID0gMS9OCn0KYGBgCgoKV2UgYXJlIG5vdyByZWFkeSB0byBwcm9jZWVkIHdpdGggdGhlICoqaW5pdGlhbGlzYXRpb24qKiBvZiB0aGUgdmFyaWFibGVzIHRoYXQgd2lsbCB1c2UgaW4gdGhlIG1haW4gbG9vcC4KCmBgYHtyIGluaXRfMiwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CnNlcF9kYXRlIDwtIGFzLkRhdGUoIjIwMTAtMDEtMDEiKSAgICAgICAgICAgICAgICAjIFRoaXMgZGF0ZSBzZXBhcmF0ZXMgaW4tc2FtcGxlIHZzIG91dC1vZi1zYW1wbGUKdF9vb3MgPC0gdF9hbGxbdF9hbGwgPiBzZXBfZGF0ZV0gICAgICAgICAgICAgICAgICMgT3V0LW9mLXNhbXBsZSBkYXRlcyAoaS5lLiwgdGVzdGluZyBzZXQpCnBvcnRmX3dlaWdodHMgPC0gbWF0cml4KDAsIG5yb3cgPSBsZW5ndGgodF9vb3MpLCAjIFdpbGwgc3RvcmUgcG9ydGZvbGlvIHdlaWdodHMKICAgICAgICAgICAgICAgICAgICAgICAgICAgbmNvbCA9IGxlbmd0aCh0aWNrKSkgCnBvcnRmX3JldHVybnMgPC0gYygpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEluaXRpYWxpemUgcG9ydGZvbGlvIHJldHVybnMKYGBgCgoKQXQgbGFzdCwgd2UgY2FuIHByb2NlZWQgdG8gdGhlIG1haW4gbG9vcC4gQSBub3RlIG9mIGNhdXRpb246IGJvdGggaW4gdGhlIHdlaWdodGluZyBzY2hlbWUgZnVuY3Rpb25zIGFuZCBpbiB0aGUgbG9vcCBiZWxvdywgd2UgYXNzdW1lIHdlbGwgZGVmaW5lZCAoZmluaXRlLCBpLmUuLCBub24gTkEpIGRhdGEuIE9idmlvdXNseSwgZmVlZGluZyAqKk5BKiogZGF0YSBpbiB0aGUgc3lzdGVtIHdpbGwgcHJvZHVjZSAqKk5BKiogb3V0cHV0cy4gVGhlcmUgYXJlIG9ubHkgZm91ciBzdGVwcyBpbiB0aGUgbG9vcDogIAoKMS4gZXh0cmFjdCB0aGUgZGF0YSAgCjIuIGNvbXB1dGUgcG9ydGZvbGlvIHdlaWdodHMgIAozLiBjb21wdXRlIHJlYWxpc2VkIHJldHVybnMgIAo0LiBkZXJpdmUgdGhlIHJldHVybiBvZiB0aGUgcG9ydGZvbGlvCgpgYGB7ciBtYWluX2xvb3AsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpmb3IodCBpbiAxOmxlbmd0aCh0X29vcykpewogIHRlbXBfZGF0YSA8LSByZXR1cm5zICU+JSBmaWx0ZXIoRGF0ZSA8IHRfb29zW3RdKSAjIDEpIEV4dHJhY3RpbmcgcGFzdCBkYXRhOiBleHBhbmRpbmcgd2luZG93ISAKICBwb3J0Zl93ZWlnaHRzW3QsXSA8LSB0ZW1wX2RhdGEgJT4lICAgICAgICAgICAgICAgIyAyKSBUYWtlIHRoaXMgcGFzdCBkYXRhIAogICAgc2VsZWN0KC1EYXRlKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgVGFrZSBvdXQgdGhlIGRhdGUgY29sdW1uCiAgICBuYS5vbWl0KCkgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBSZW1vdmUgbWlzc2luZyBwb2ludHMKICAgIHdlaWdodHNfbXNyKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEFwcHBseSB0aGUgd2VpZ2h0aW5nIHNjaGVtZSBmdW5jdGlvbgogIHJlYWxpc2VkX3JldHVybnMgPC0gcmV0dXJucyAlPiUgICAgICAgICAgICAgICAgICAjIDMpIFRha2UgcmV0dXJucwogICAgZmlsdGVyKERhdGUgPT0gIHRfb29zW3RdKSAlPiUgICAgICAgICAgICAgICAgICAgICMgS2VlcCBvbmx5IGN1cnJlbnQgZGF0ZQogICAgc2VsZWN0KC1EYXRlKSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgVGFrZSBvdXQgdGhlIGRhdGUgY29sdW1uCiAgcG9ydGZfcmV0dXJuc1t0XSA8LSBzdW0ocG9ydGZfd2VpZ2h0c1t0LF0gKiByZWFsaXNlZF9yZXR1cm5zKSAjIDQpIENvbXB1dGUgdGhlIHJldHVybgp9CmBgYAoKSW4gdGhlIGFib3ZlICoqYmFja3Rlc3QqKiwgdGhlIGFtb3VudCBvZiBkYXRhIGNvbnNpZGVyZWQgdG8gZm9ybSB0aGUgcG9ydGZvbGlvIGRlY2lzaW9uIGluY3JlYXNlcyB3aXRoIHRpbWUgKCoqZXhwYW5kaW5nIHdpbmRvdyoqKS4gSXQgaXMgZWFzeSB0byBmaXggdGhlIG51bWJlciBvZiBkYXRhIHBvaW50IGF0IGVhY2ggc3RlcCBhbmQgcHJvY2VlZCBvbiByb2xsaW5nIHdpbmRvd3MgKGV4ZXJjaXNlKS4gTGlrZXdpc2UsIHN3aXRjaGluZyBmcm9tICoqTVNSKiogdG8gKipFVyoqIGlzIGltbWVkaWF0ZSAoanVzdCBjaGFuZ2UgdGhlIHdlaWdodGluZyBmdW5jdGlvbikuICAKClRoZSBtYWluIG91dHB1dCBpcyB0aGUgdmVjdG9yIG9mIHBvcnRmb2xpbyByZXR1cm5zLiBXZSBjYW4gZWFzaWx5IHBsb3QgdGhlICoqZXZvbHV0aW9uKiogb2YgdGhlIHBvcnRmb2xpbyB0aHJvdWdoIHRpbWUuCgpgYGB7ciBwb3J0X3Bsb3QsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpwb3J0IDwtIGRhdGEuZnJhbWUoRGF0ZSA9IHRfb29zLCAKICAgICAgICAgICAgICAgICAgIFBvcnRmb2xpbyA9IGN1bXByb2QoMStwb3J0Zl9yZXR1cm5zKSkgICAgIyBQb3J0Zi4gdmFsdWVzIHZpYSBjdW11bGF0aXZlIHByb2R1Y3QKcG9ydCAlPiUgZ2dwbG90KCkgKyB0aGVtZV9saWdodCgpICsKICBnZW9tX2xpbmUoYWVzKHggPSBEYXRlLCB5ID0gUG9ydGZvbGlvKSkgICAgICAgICAgICAgICAgICAgIyBQbG90CmBgYAoKCkJlbG93LCB3ZSBjcmVhdGUgYSBmdW5jdGlvbiB0aGF0IHRha2VzIGEgc2VyaWVzIG9mIHJldHVybnMgYXMgaW5wdXQgYW5kIHByb3ZpZGVzIGEgZmV3IHNpbXBsZSAqKnBlcmZvcm1hbmNlIG1ldHJpY3MqKi4KCmBgYHtyIHBlcmZfbWV0LCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KcGVyZl9tZXQgPC0gZnVuY3Rpb24ocmV0dXJucyl7CiAgYXZnX3JldCA8LSBtZWFuKHJldHVybnMsIG5hLnJtID0gVCkgICAgICAgICAgICAgICAgICAgICAjIEFyaXRobWV0aWMgbWVhbiAKICB2b2wgPC0gc2QocmV0dXJucywgbmEucm0gPSBUKSAgICAgICAgICAgICAgICAgICAgICAgICAgICMgVm9sYXRpbGl0eQogIFNoYXJwZV9yYXRpbyA8LSBhdmdfcmV0IC8gdm9sICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBTaGFycGUgcmF0aW8KICBWYVJfNSA8LSBxdWFudGlsZShyZXR1cm5zLCAwLjA1KSAgICAgICAgICAgICAgICAgICAgICAgICMgVmFsdWUtYXQtcmlzawogIG1ldCA8LSBkYXRhLmZyYW1lKGF2Z19yZXQsIHZvbCwgU2hhcnBlX3JhdGlvLCBWYVJfNSkgICAgIyBBZ2dyZWdhdGlvbiBvZiBhbGwgb2YgdGhpcwogIHJvd25hbWVzKG1ldCkgPC0gIm1ldHJpY3MiCiAgcmV0dXJuKG1ldCkKfQpwZXJmX21ldChwb3J0Zl9yZXR1cm5zKSAjIExldCdzIHRlc3Qgb24gdGhlIGFjdHVhbCByZXR1cm5zCmBgYAoKTm90ZTogdGhlIHZhbHVlcyBhcmUgKipub3QgYW5udWFsaXNlZCoqLiBUaGUgYW5udWFsaXNhdGlvbiBjYW4gYmUgZGlyZWN0bHkgY29kZWQgaW50byB0aGUgZnVuY3Rpb24uIEEgaGV1cmlzdGljIHdheSB0byBwcm9jZWVkIGlzIHRvIG11bHRpcGx5IGF2ZXJhZ2UgcmV0dXJucyBieSAxMiBhbmQgdm9sYXRpbGl0aWVzIGJ5ICRcc3FydHsxMn0kIC0gdGhvdWdoIHRoaXMgb21pdHMgdGhlIGNvbXBvdW5kaW5nIGVmZmVjdC4gVGhlc2Ugc2ltcGxpZmljYXRpb25zIGFyZSBvayBpZiB0aGV5IGFyZSB1c2VkIHRvIGNvbXBhcmUgc3RyYXRlZ2llcy4gVGhlIFZhbHVlIGF0IFJpc2sgaXMgbm9uZXRoZWxlc3MgZGVwZW5kZW50IG9uIHRoZSByZXR1cm4gaG9yaXpvbiBhbmQgY2Fubm90IGJlIHByb3hpZWQgc28gc2ltcGx5LiAgIAoKQW4gaW1wb3J0YW50IGluZGljYXRvciBpcyB0aGUgKip0dXJub3ZlcioqIG9mIHRoZSBwb3J0Zm9saW86IGl0IGFzc2Vzc2VzIGFzc2V0IHJvdGF0aW9uIGFuZCB0aHVzIGltcGFjdHMgdHJhbnNhY3Rpb24gY29zdHMuIFNpbXBsZSB0dXJub3ZlciBjb21wdXRlcyBhdmVyYWdlIGFic29sdXRlIHZhcmlhdGlvbiBpbiBwb3J0Zm9saW8gd2VpZ2h0czogJFx0ZXh0e1R1cm59PVxmcmFjezF9e1R9XHN1bV97dD0yfV5UXHN1bV97bj0xfV5OfHdfdF5uLXdfe3QtMX1ebnwkLiBGdWxsIHR1cm5vdmVyIHRha2VzIGludG8gYWNjb3VudCB0aGUgdmFyaWF0aW9uIG9mIHRoZSB3ZWlnaHRzIGJldHdlZW4gcmViYWxhbmNpbmcgZGF0ZXM6ICRcdGV4dHtUdXJufT1cZnJhY3sxfXtUfVxzdW1fe3Q9Mn1eVFxzdW1fe249MX1eTnx3X3Rebi13X3t0LX1ebnwkLCB3aGVyZSAkdC0kIGlzIHRoZSB0aW1lIGp1c3QgYmVmb3JlIHRoZSByZWJhbGFuY2luZyBkYXRlLiAKCmBgYHtyIHR1cm5vdmVyLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KdHVybm92ZXJfc2ltcGxlIDwtIGZ1bmN0aW9uKHdlaWdodHMsIHRfb29zKXsKICB0dXJuIDwtIDAKICBmb3IodCBpbiAyOmxlbmd0aCh0X29vcykpeyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBMb29wIG9uIGRhdGVzCiAgICB0dXJuIDwtIHR1cm4gKyBzdW0oYWJzKHdlaWdodHNbdCxdIC0gd2VpZ2h0c1t0LTEsXSkpICMgVmFyaWF0aW9uIGluIHdlaWdodHMKICB9CiAgcmV0dXJuKHR1cm4vKGxlbmd0aCh0X29vcyktMSkpICAgICAgICAgICAgICAgICAgICAgICAgICMgQkVXQVJFOiBtb250aGx5IHZhbHVlIQp9CnR1cm5vdmVyX3NpbXBsZShwb3J0Zl93ZWlnaHRzLCB0X29vcykgICAgICAgICAgICAgICAgICAgICMgU2ltcGxlIHR1cm5vdmVyIQpgYGAKCkJlbG93LCB3ZSBzd2l0Y2ggdG8gdGhlIGZ1bGwgZGVmaW5pdGlvbiBvZiB0aGUgKip0dXJub3ZlcioqLiBJbiB0aGlzIGNhc2UsIHRoZSB2YXJpYXRpb24gaW4gd2VpZ2h0cyBpcyBhZGp1c3RlZCBiZWNhdXNlIHRoZSB3ZWlnaHQgcHJpb3IgdG8gcmViYWxhbmNpbmcgaGF2ZSBkcmlmdGVkLgoKYGBge3IgdHVybm92ZXJfZnVsbCwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CnR1cm5vdmVyX2Z1bGwgPC0gZnVuY3Rpb24od2VpZ2h0cywgYXNzZXRfcmV0dXJucywgdF9vb3MpewogIHR1cm4gPC0gMAogIGZvcih0IGluIDI6bGVuZ3RoKHRfb29zKSl7CiAgICByZWFsaXNlZF9yZXR1cm5zIDwtIHJldHVybnMgJT4lIGZpbHRlcihEYXRlID09IHRfb29zW3RdKSAlPiUgc2VsZWN0KC1EYXRlKQogICAgcHJpb3Jfd2VpZ2h0cyA8LSB3ZWlnaHRzW3QtMSxdICogKDEgKyByZWFsaXNlZF9yZXR1cm5zKSAgICAgICAjIEJlZm9yZSByZWJhbGFuY2luZwogICAgdHVybiA8LSB0dXJuICsgYXBwbHkoYWJzKHdlaWdodHNbdCxdIC0gcHJpb3Jfd2VpZ2h0cy9zdW0ocHJpb3Jfd2VpZ2h0cykpLDEsc3VtKQogIH0KICByZXR1cm4odHVybi8obGVuZ3RoKHRfb29zKS0xKSkKfQphc3NldF9yZXR1cm5zIDwtIHJldHVybnMgJT4lIGZpbHRlcihEYXRlID4gc2VwX2RhdGUpICAgICMgQXNzZXQgcmV0dXJucyBvdmVyIHRoZSBleHBlcmltZW50CnR1cm5vdmVyX2Z1bGwocG9ydGZfd2VpZ2h0cywgYXNzZXRfcmV0dXJucywgdF9vb3MpICAgICAgIyBSZWFsIHR1cm5vdmVyCmBgYAoKTm90ZSB0aGF0IHRoZSB0dXJub3ZlciBpcyBjb21wdXRlZCBhdCB0aGUgKiptb250aGx5IGZyZXF1ZW5jeSoqLiBUaGUgc2Vjb25kIHZhbHVlIGlzIGFsd2F5cyBtb3JlIHJlYWxpc3RpYzsgaW4gdGhpcyBjYXNlIGl0IGlzIHN1YnN0YW50aWFsbHkgaGlnaGVyIGNvbXBhcmVkIHRvIHRoZSBzaW1wbGlmaWVkIHByb3h5LiBGb3IgdGhlIHNha2Ugb2YgY29tcGFjdG5lc3MsIHRoZSB0dXJub3ZlciBzaG91bGQgYmUgaW5jbHVkZWQgaW4gdGhlICoqcGVyZl9tZXQqKigpIGZ1bmN0aW9uLgoKCiMgRXh0ZW5zaW9ucwojIyBDb21wYXJpbmcgc3RyYXRlZ2llcwoKQW4gaW1wb3J0YW50IGdlbmVyYWxpc2F0aW9uIG9mIHRoZSBhYm92ZSBmcmFtZXdvcmsgaXMgdG8gY29uc2lkZXIgKiptb3JlIHRoYW4gb25lIHN0cmF0ZWd5KiouIENvbXBhcmlzb25zIGFyZSBjb21tb25wbGFjZSBpbiB0aGUgYXNzZXQgbWFuYWdlbWVudCBpbmR1c3RyeTogb2J2aW91c2x5LCBwZW9wbGUgbG9vayBmb3IgdGhlICpiZXN0KiBzdHJhdGVneSAoYWNjb3JkaW5nIHRvIHBhcnRpY3VsYXIgZ29hbHMsIGJlbGllZnMsIGFuZCBwcmVmZXJlbmNlcykuIEJlbG93LCB3ZSBzaG93IGhvdyB0aGlzIGNhbiBiZSBoYW5kbGVkLiBXZSB3aWxsIGNvbXBhcmUgdGhlIHR3byBzdHJhdGVnaWVzIHRoYXQgd2UgbWVudGlvbm5lZCBhYm92ZS4KRmlyc3QsIHdlIG5lZWQgdG8gcmUtaW5pdGlhdGUgdGhlIHZhcmlhYmxlcyBiZWNhdXNlIHRoZWlyIGRpbWVuc2lvbiB3aWxsIGNoYW5nZSAoKipOT1RFKio6IGFuIGFsdGVybmF0aXZlIHJvdXRlIHdvdWxkIGJlIHRvIHdvcmsgd2l0aCBsaXN0cykuIAoKYGBge3IgbXVsdGlfaW5pdCwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9ClR0IDwtIGxlbmd0aCh0X29vcykgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIE5iIG9mIGNvbXB1dGF0aW9uIGRhdGVzIAojIEF2b2lkIFQgYmVjYXVzZSBUID0gVFJVRSEKbmJfcG9ydCA8LSAyICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgTmIgb2YgcG9ydGZvbGlvcwpwb3J0Zl93ZWlnaHRzIDwtIGFycmF5KDAsIGRpbSA9IGMoVHQsIG5iX3BvcnQsIGxlbmd0aCh0aWNrKSkpICAgIyBTdG9yZSB3ZWlnaHRzCnBvcnRmX3JldHVybnMgPC0gbWF0cml4KDAsIG5yb3cgPSBUdCwgbmNvbCA9IG5iX3BvcnQpICAgICAgICAgICAjIFN0b3JlIHJldHVybnMKYGBgCgpTZWNvbmQsIHdlIGVtYmVkIGFsbCB3ZWlnaHRpbmcgc2NoZW1lcyBpbnRvIG9uZSBzaW5nbGUgZnVuY3Rpb24uCgpgYGB7ciBtdWx0aV93ZWlnaHRzfQp3ZWlnaHRzX211bHRpIDwtIGZ1bmN0aW9uKHJldHVybnMsIGopeyAgICMgU3RyYXRlZ2llcyBhcmUgaW5kZXhlZCBieSBqCiAgaWYoaiA9PSAxKXsgIyBqID0gMSA9PiBNU1IKICAgIHJldHVybih3ZWlnaHRzX21zcihyZXR1cm5zKSkKICB9CiAgaWYoaiA9PSAyKXsgIyBqID0gMiA9PiBFVwogICAgTiA8LSBsZW5ndGgocmV0dXJuc1sxLF0pCiAgICByZXR1cm4ocmVwKDEvTixOKSkKICB9Cn0KYGBgCgpXZSBkZWNpZGVkIHRvIHJlY29kZSB0aGUgKipFVyoqIHN0cmF0ZWd5LCBidXQgd2UgY291bGQgaGF2ZSB1c2VkIHRoZSAqKndlaWdodHNfZXcqKigpIGZ1bmN0aW9uIGluc3RlYWQuCkZpbmFsbHksIHRoZSBtYWluIGxvb3AgaXMgb25seSBtYXJnaW5hbGx5IGRpZmZlcmVudCBmcm9tIHRoZSBzaW5nbGUgc3RyYXRlZ3kgbG9vcC4KCmBgYHtyIG11bHRpX2xvb3AsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpmb3IodCBpbiAxOmxlbmd0aCh0X29vcykpewogIHRlbXBfZGF0YSA8LSByZXR1cm5zICU+JSAKICAgIGZpbHRlcihEYXRlIDwgdF9vb3NbdF0pICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAjIFNhbWUgZmlyc3Qgc3RlcAogICAgbmEub21pdCgpICU+JSAKICAgIHNlbGVjdCgtRGF0ZSkKICByZWFsaXNlZF9yZXR1cm5zIDwtIHJldHVybnMgJT4lICAgICAgICAgICAgICAgICAgICAgICAjIFNhbWUgdGhpcmQgc3RlcDogcmV0dXJucwogICAgZmlsdGVyKERhdGUgPT0gIHRfb29zW3RdKSAlPiUgCiAgICBzZWxlY3QoLURhdGUpCiAgZm9yKGogaW4gMTpuYl9wb3J0KXsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBUaGlzIGlzIHRoZSBub3ZlbHR5OiB3ZSBsb29wIG9uIHRoZSBzdHJhdGVnaWVzIAogICAgcG9ydGZfd2VpZ2h0c1t0LGosXSA8LSB3ZWlnaHRzX211bHRpKHRlbXBfZGF0YSwgaikgICMgVGhlIHdlaWdodHMnIGZ1bmN0aW9uIGlzIGluZGV4ZWQgYnkgagogICAgcG9ydGZfcmV0dXJuc1t0LGpdIDwtIHN1bShwb3J0Zl93ZWlnaHRzW3QsaixdICogcmVhbGlzZWRfcmV0dXJucykKICB9Cn0KYXBwbHkocG9ydGZfcmV0dXJucywgMiwgcGVyZl9tZXQpICU+JSAgICAgICAgICAgICAgICAgICAjIFRha2luZyBwZXJmIG1ldHJpY3MKICB1bmxpc3QoKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEZsYXR0ZW5pbmcgdGhlIGxpc3QKICBtYXRyaXgobnJvdyA9IDIsIGJ5cm93ID0gVCkgJT4lICAgICAgICAgICAgICAgICAgICAgICAjIE9yZGVyaW5nIHRoZW0KICBgY29sbmFtZXM8LWAoYygiYXZnX3JldCIsICJ2b2wiLCAiU1IiLCAiVmFSIikpICU+JSAgICAjIEFkZGluZyBjb2x1bW4gbmFtZXMKICBkYXRhLmZyYW1lKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIENvbnZlcnRpbmcgdG8gZGF0YWZyYW1lCmFwcGx5KHBvcnRmX3dlaWdodHMsIDIsIHR1cm5vdmVyX3NpbXBsZSwgdF9vb3MgPSB0X29vcykgJT4lIHVubGlzdCgpCmBgYAoKV2UgcmVjYWxsIHRoZSBvcmRlciBvZiBzdHJhdGVnaWVzOiAqKk1TUioqIGZpcnN0IChsaW5lKSBhbmQgKipFVyoqIHNlY29uZCAobGluZSkuICAKCkFnYWluLCB0dXJub3ZlciBzaG91bGQgKGFuZCB3aWxsKSBiZSBhZGRlZCB0byB0aGUgcGVyZm9ybWFuY2UgbWV0cmljIGZ1bmN0aW9uLiBTaW5jZSB1bmlmb3JtIHdlaWdodHMgYXJlIGNvbnN0YW50LCB0aGVpciBzaW1wbGlmaWVkIHR1cm5vdmVyIGlzIHplcm8uIEluIHByYWN0aWNlLCB0aGF0IGlzIG5vdCB0aGUgY2FzZSBiZWNhdXNlIHdlaWdodHMgZXZvbHZlIGFjY29yZGluZyB0byBhc3NldCByZXR1cm5zLiBUaGUgYWRqdXN0bWVudCB3b3VsZCBpbXBseSBvbmx5IGEgc21hbGwgdHVybm92ZXIuCgpUaGVyZSBpcyBhIHdlbGwtZG9jdW1lbnRlZCAqKnN1YnN0YW50aWFsIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgdHdvIHdlaWd0aW5nIHNjaGVtZXMqKiBpbiB0ZXJtcyBvZiBhc3NldCByb3RhdGlvbi4gVGhlIE1TUiB0aGF0IHdlIGNvbXB1dGUgaXMgY2xlYXJseSBub3QgY29tcGV0aXRpdmU6IGV2ZW4gYmVmb3JlIHRyYW5zYWN0aW9uIGNvc3RzLCBpdHMgU2hhcnBlIHJhdGlvIGlzIHNtYWxsZXIgdGhhbiB0aGF0IG9mIHRoZSBFVyBwb3J0Zm9saW8gKHNlZSBEZU1pZ3VlbCBldCBhbC4gKDIwMDkpIGZvciBmdXJ0aGVyIGV2aWRlbmNlIG9uIHRoZSByb2J1c3RuZXNzIG9mIHRoZSBFVyBwb3J0Zm9saW8pLgoKCgoKIyMgTWFrZSBkbyB3aXRob3V0IGxvb3BzOiBmdW5jdGlvbmFsIHByb2dyYW1taW5nCgpGaW5hbGx5LCB3ZSBzaG93IGhvdyB0byAqKmJ5cGFzcyB0aGUgbG9vcCoqIG92ZXIgZGF0ZXMuIFdoaWxlIHRoaXMgaXMgbm90IHVzZWZ1bCBvbiBzbWFsbCBkYXRhc2V0cywgaXQgY2FuIHNhdmUgdGltZSBvbiBsYXJnZSBkYXRhYmFzZXMgYmVjYXVzZSBsb29wcyBhcmUgbm90b3Jpb3VzbHkgdGltZS1jb25zdW1pbmcuIEJlbG93LCB3ZSBzaG93IGhvdyB0byBwcm9jZWVkIHdpdGggdGhlICoqbWFwKiooKSBmdW5jdGlvbiBpbiB0aGUgc2ltcGxlIGNhc2Ugd2l0aCBvbmx5IG9uZSBzdHJhdGVneS4KCmBgYHtyIG1hcCwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CiMgV2UgY3JlYXRlIGEgZnVuY3Rpb24gdGhhdCB3aWxsIGNvbXB1dGUgcmV0dXJucyBmb3IgZWFjaCBkYXRlOgpwb3J0X21hcCA8LSBmdW5jdGlvbih0X29vcywgcmV0dXJucywgd2VpZ2h0X2Z1bmMpeyAjIFdlaWdodGluZyBmdW5jdGlvbiBhcyBhcmd1bWVudCEgICAgICAgICAgICAgCiAgdGVtcF9kYXRhIDwtIHJldHVybnMgJT4lIGZpbHRlcihEYXRlIDwgdF9vb3MpICAgICMgU3RpbGwgZXhwYW5kaW5nIHdpbmRvdy4uLgogIHBvcnRmX3dlaWdodHMgPC0gdGVtcF9kYXRhICU+JSAKICAgIHNlbGVjdCgtRGF0ZSkgJT4lIAogICAgbmEub21pdCgpICU+JQogICAgd2VpZ2h0X2Z1bmMoKQogIHJlYWxpc2VkX3JldHVybnMgPC0gcmV0dXJucyAlPiUgCiAgICBmaWx0ZXIoRGF0ZSA9PSAgdF9vb3MpICU+JSAKICAgIHNlbGVjdCgtRGF0ZSkKICByZXR1cm4oc3VtKHBvcnRmX3dlaWdodHMgKiByZWFsaXNlZF9yZXR1cm5zKSkKfQojIHRoZSBtYXAoKSBmdW5jdGlvbiBkb2VzIGl0IGFsbCEKcG9ydGZfcmV0dXJucyA8LSB0X29vcyAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgIyBUaGUgdmFyaWFibGUgb3ZlciB3aGljaCB3ZSBsb29wCiAgbWFwKH5wb3J0X21hcCgueCwgCiAgICAgICAgICAgICAgICByZXR1cm5zID0gcmV0dXJucywgCiAgICAgICAgICAgICAgICB3ZWlnaHRfZnVuYyA9IHdlaWdodHNfbXNyKSAgICAgICAgICMgTVNSIHdlaWdodHMKICApICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBJcyBzZW50IHRvIHRoZSBtYXAoKSBmdW5jdGlvbgogIHVubGlzdCgpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRoZSBvdXRwdXQgaXMgZmxhdHRlbmVkCnBlcmZfbWV0KHBvcnRmX3JldHVybnMpICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgQ29tcHV0ZSB0aGUgcGVyZiBtZXRyaWNzCmBgYAoKCgojIENoYXJhY3RlcmlzdGljcy1iYXNlZCBwb3J0Zm9saW8gY2hvaWNlCgpJbiB0aGlzIHNlY3Rpb24sIHdlIHN0YXJ0IHRoZSBjaGFwdGVyIG9mIHN0cmF0ZWdpZXMgYmFzZWQgb24gZmlybSBjaGFyYWN0ZXJpc3RpY3MgKCoqZmVhdHVyZXMqKikuIEFzIGFuIGlsbHVzdHJhdGlvbiwgd2UgY2hlY2sgYSB3ZWxsLWRvY3VtZW50ZWQgKHRob3VnaCBzdGlsbCBjb250cm92ZXJzaWFsKSAqKmFub21hbHkqKjogdGhlICoqc2l6ZSBlZmZlY3QqKi4gV2UgYnVpbGQgdHdvIHBvcnRmb2xpb3M6IGluIHRoZSBmaXJzdCAoKnJlc3AqLiBzZWNvbmQpIG9uZSwgd2UgaW52ZXN0IGluIHRoZSBmaXJtcyB0aGF0IGhhdmUgYSBiZWxvdyAoKnJlc3AqLiBhYm92ZSkgbWVkaWFuIG1hcmtldCBjYXBpdGFsaXNhdGlvbi4gVGhlIGZpcnN0IHBvcnRmb2xpbyB3aWxsIGJlIGEgJ3NtYWxsJyBwb3J0Zm9saW8gYW5kIHRoZSBzZWNvbmQgb25lIGEgJ2xhcmdlJyBvbmUuIFN0b2NrcyBhcmUgZXF1YWxseS13ZWlnaHRlZCBpbnNpZGUgdGhlIHBvcnRmb2xpb3MuCgpGaXJzdCwgd2UgcHJlcGFyZSB0aGUgdmFyaWFibGVzIGFuZCBkZWZpbmUgdGhlICoqd2VpZ2h0IGZ1bmN0aW9uKiouCgpgYGB7ciBjaGFyc18xLCB3YXJuaW5ncyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9Cm5iX3BvcnQgPC0gMiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgTmIgb2YgcG9ydGZvbGlvcwpwb3J0Zl93ZWlnaHRzIDwtIGFycmF5KDAsIGRpbSA9IGMoVHQtMSwgbmJfcG9ydCwgbGVuZ3RoKHRpY2spKSkgICAjIFdoZXJlIHdlIHN0b3JlIHdlaWdodHMKcG9ydGZfcmV0dXJucyA8LSBtYXRyaXgoMCwgbnJvdyA9IFR0LTEsIG5jb2wgPSBuYl9wb3J0KSAgICAgICAgICAgIyBXaGVyZSB3ZSBzdG9yZSByZXR1cm5zCgp3ZWlnaHRzX2NhcCA8LSBmdW5jdGlvbihkYXRhLGopeyAgICAKICAjIE1vcmUgZ2VuZXJhbCB0aGFuIGJlZm9yZTogd2UgZmVlZCBhbGwgdGhlIGRhdGEsIG5vdCBqdXN0IHJldHVybnMKICBtIDwtIG1lZGlhbihkYXRhJE1rdF9DYXApICAgICAgICMgQ29tcHV0ZSB0aGUgbWVkaWFuIG1hcmtldCBjYXAKICBuIDwtIG5yb3coZGF0YSkgICAgICAgICAgICAgICAgICMgQ29tcHV0ZSB0aGUgbnVtYmVyIG9mIGFzc2V0cwogIGlmKGogPT0gMSl7cmV0dXJuKChkYXRhJE1rdF9DYXAgPCBtKS9uKjIpfSAjIFNtYWxsIGNhcAogIGlmKGogPT0gMil7cmV0dXJuKChkYXRhJE1rdF9DYXAgPiBtKS9uKjIpfSAjIExhcmdlIGNhcAp9CmBgYAoKVGhlcmUgd2lsbCBvbmx5IGJlIFR0LTEgZGF0ZXMgc2luY2Ugd2UgbG9zZSBvbmUgYmVjYXVzZSBvZiB0aGUgY29tcHV0YXRpb24gb2YgZnV0dXJlIHJldHVybnMuICAKClNlY29uZCwgd2UgY2FuIGxhdW5jaCB0aGUgKipiYWNrdGVzdGluZyBsb29wKiouCgpgYGB7ciBjaGFyc18yLCB3YXJuaW5ncyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CmZvcih0IGluIDI6bGVuZ3RoKHRfb29zKSl7CiAgdGVtcF9kYXRhIDwtIGRhdGEgJT4lIGZpbHRlcihEYXRlID09IHRfb29zW3QtMV0pICAgICAgICAjIFdlIGtlZXAgdGhlIGRhdGEgb2YgdGhlIHByZXZpb3VzIGRhdGUKICBmb3IoaiBpbiAxOm5iX3BvcnQpeyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgV2UgbG9vcCBvbiB0aGUgc3RyYXRlZ2llcyAKICAgIHBvcnRmX3dlaWdodHNbdC0xLGosXSA8LSB3ZWlnaHRzX2NhcCh0ZW1wX2RhdGEsIGopICAgICMgVGhlIHdlaWdodHMnIGZ1bmN0aW9uIGlzIGluZGV4ZWQgYnkgagogICAgcmVhbGlzZWRfcmV0dXJucyA8LSByZXR1cm5zICU+JSAKICAgICAgZmlsdGVyKERhdGUgPT0gIHRfb29zW3RdKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICMgU2hpZnQgaW4gdGhlIGRhdGUKICAgICAgbmEub21pdCgpICU+JSAKICAgICAgc2VsZWN0KC1EYXRlKQogICAgcG9ydGZfcmV0dXJuc1t0LTEsal0gPC0gc3VtKHBvcnRmX3dlaWdodHNbdC0xLGosXSAqIHJlYWxpc2VkX3JldHVybnMpCiAgfQp9CmBgYAoKVGhpcmQsIHdlIHByb2NlZWQgdG8gcGVyZm9ybWFuY2UgbWV0cmljcy4KCmBgYHtyIGNoYXJzXzMsIHdhcm5pbmdzID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KYXBwbHkocG9ydGZfcmV0dXJucywgMiwgcGVyZl9tZXQpICU+JSAgICAgICAgICAgICAgICAgICAjIFRha2luZyBwZXJmIG1ldHJpY3MKICB1bmxpc3QoKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEZsYXR0ZW5pbmcgdGhlIGxpc3QKICBtYXRyaXgobnJvdyA9IDIsIGJ5cm93ID0gVCkgJT4lICAgICAgICAgICAgICAgICAgICAgICAjIE9yZGVyaW5nIHRoZW0KICBgY29sbmFtZXM8LWAoYygiYXZnX3JldCIsICJ2b2wiLCAiU1IiLCAiVmFSIikpICU+JSAgICAjIEFkZGluZyBjb2x1bW4gbmFtZXMKICBkYXRhLmZyYW1lKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIENvbnZlcnRpbmcgdG8gZGF0YWZyYW1lCmBgYAoKU21hbGwgZmlybXMgZG8gaW5kZWVkIGdlbmVyYXRlIGEgaGlnaGVyIGxldmVsIG9mIHBlcmZvcm1hbmNlISBJbiBvcmRlciB0byByZWFjaCB0aGlzIGNvbmNsdXNpb24gaW4gYSByaWdvdXJvdXMgZmFzaGlvbiwgd2Ugd291bGQgbmVlZCB0byBwZXJmb3JtIHRoZSBzYW1lIGFuYWx5c2lzIG9uIGF0IGxlYXN0IDEsMDAwIHN0b2NrcyAoaWRlYWxseSwgbW9yZSkgYW5kIG9uIDUgdG8gMTAgcG9ydGZvbGlvIHNvcnRzIChmcm9tIHZlcnkgc21hbGwgZmlybXMgdG8gdmVyeSBsYXJnZSBvbmVzKS4gQmVsb3csIHdlIGNoZWNrIHRoZSB3ZWlnaHRzIG9mIHRoZSBwb3J0Zm9saW8gb24gb25lIHBhcnRpY3VsYXIgZGF0ZS4KCmBgYHtyIGNoZWNrLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0Kc21hbGwgPC0gcG9ydGZfd2VpZ2h0c1syLDEsXSAjIHQgPSAyLCBqID0gMSAodF9vb3NbMl0gPSAyMDEwLTAzLTAxLCBzbWFsbCBmaXJtcykKbGFyZ2UgPC0gcG9ydGZfd2VpZ2h0c1syLDIsXSAjIHQgPSAyLCBqID0gMiAodF9vb3NbMl0gPSAyMDEwLTAzLTAxLCBsYXJnZSBmaXJtcykKZGF0YS5mcmFtZShzbWFsbCwgbGFyZ2UsIHJvdy5uYW1lcyA9IHRpY2spCmBgYAoKSW5kZWVkLCBzb21lIHN0b2NrcyBoYXZlIHplcm8gd2VpZ2h0cyBhbmQgb3RoZXJzIDEvMTUuICAKCkZpbmFsbHksIGxldCdzIHNlZSBob3cgd2UgY291bGQgaGF2ZSBjb2RlZCB0aG9zZSBzdHJhdGVnaWVzIHVzaW5nIHRoZSAqKnRpZHl2ZXJzZSoqIChhbmQgYSBsb3Qgb2YgcGlwaW5nISkuCgpgYGB7ciBwaXZvdCEsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpkYXRhICU+JSBmaWx0ZXIoRGF0ZSA+IHNlcF9kYXRlKSAlPiUgICAgICAgICAgICAgICAgICAgICAgIyBLZWVwIG9ubHkgdGhlIG91dC1vZi1zYW1wbGUgYmFja3Rlc3RpbmcgZGF0ZXMKICBncm91cF9ieShUaWNrKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgR3JvdXAgYnkgc3RvY2sKICBtdXRhdGUoRl9SZXR1cm4gPSBkcGx5cjo6bGVhZChSZXR1cm4pKSAlPiUgICAgICAgICAgICAgICMgQ29tcHV0ZSBmb3J3YXJkIChpLmUuLCByZWFsaXNlZCkgcmV0dXJuCiAgbmEub21pdCgpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRha2Ugb3V0IE5BcwogIGdyb3VwX2J5KERhdGUpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBHcm91cCBieSBkYXRlcwogIG11dGF0ZShNa3RfQ2FwX0JpbmFyeSA9IE1rdF9DYXAgPCBtZWRpYW4oTWt0X0NhcCkpICU+JSAgIyBDb21wdXRlIG1lZGlhbiBjYXAgZm9yIGVhY2ggZGF0ZQogIHVuZ3JvdXAoKSAlPiUKICBncm91cF9ieShNa3RfQ2FwX0JpbmFyeSkgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgR3JvdXAgYnkgTWt0X0NhcDogc21hbGwgdnMgbGFyZ2UKICBzdW1tYXJpc2UoYXZnX3JldHVybiA9IG1lYW4oRl9SZXR1cm4pKSAgICAgICAgICAgICAgICAgICMgU2ltcGxlIHBpdm90IHRhYmxlCmBgYAoKCkl0IGNhbiBiZSB1c2VmdWwgdG8gc2VlIGhvdyBvZnRlbiBzdG9ja3Mgc3dpdGNoIGZyb20gb25lIGZhbWlseSB0byBhbm90aGVyIChmcm9tIGJlbG93IG1lZGlhbiB0byBhYm92ZSBtZWRpYW4gb3IgdmljZS12ZXJzYSkuIEJlbG93LCB3ZSBzaG93IGEgcGxvdCBvZiAqKk1rdF9DYXAqKiwgY29uZGl0aW9uYWwgb24gKipNa3RfQ2FwKiogYmVpbmcgYWJvdmUgdGhlIGN1cnJlbnQgbWVkaWFuLiAKCmBgYHtyIGNhcF9ncmFwaCwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CmRhdGEgJT4lIGdyb3VwX2J5KERhdGUpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgIyBHcm91cCBieSBkYXRlCiAgbXV0YXRlKE1rdF9DYXBfbWVkaWFuID0gbWVkaWFuKE1rdF9DYXApKSAlPiUgICAgICAgIyBDb21wdXRlIG1lZGlhbiBjYXAgZm9yIGVhY2ggZGF0ZQogIGZpbHRlcihNa3RfQ2FwID4gTWt0X0NhcF9tZWRpYW4pICU+JSAgICAgICAgICAgICAgICMgS2VlcCBvbmx5IHRoZSBsYXJnZSBzdG9ja3MKICBnZ3Bsb3QoYWVzKHggPSBEYXRlLCB5ID0gTWt0X0NhcCwgY29sb3IgPSBUaWNrKSkgKyAjIFBsb3QKICBnZW9tX2xpbmUoKSArIHlsaW0oNzUwMDAsMjUwMDAwKSArCiAgZ2VvbV9saW5lKGFlcyh4ID0gRGF0ZSwgeSA9IE1rdF9DYXBfbWVkaWFuKSwgY29sb3IgPSAiYmxhY2siKSAKIyBUaGUgYmxhY2sgbGluZSBzaG93cyB0aGUgcnVubmluZyBtZWRpYW4KYGBgCgpUaGUgc3RyYWlnaHQgbGluZXMgc2hvdyB0aGUgKipkaXNjb250aW51aXRpZXMqKjogb25lIHN0b2NrIGJlaW5nIGxhcmdlIGF0IHNvbWUgcG9pbnQgaW4gdGltZSwgdGhlbiBzbWFsbCBhbmQgdGhlbiBsYXJnZSBhZ2Fpbi4gVGhlIHN0cmFpZ2h0IGxpbmVzIHNob3cgdGhlIHBlcmlvZHMgd2hlbiB0aGUgc3RvY2sgd2FzIHNtYWxsLiBUaGUgYmxhY2sgbGluZSBzaG93cyB0aGUgbWVkaWFuIGNhcGl0YWxpc2F0aW9uIChpbiB0aGUgc2FtcGxlKS4gRmluYWxseSwgYmVjYXVzZSB3ZSBmb2N1cyBpbiB0aGUgem9uZSBjbG9zZSB0byB0aGUgbWVkaWFuIGFuZCBpbXBvc2UgYW4gdXBwZXIgbGltaXQgb2YgMjUwQiQsIHRoZXJlIGFyZSBzb21lIG1pc3NpbmcgcG9pbnRzLgoKCgoKIyBTdXN0YWluYWJsZSBpbnZlc3RpbmcKCioqRVNHKiogaW52ZXN0aW5nIGhhcyBnYWluZWQgYSBsb3Qgb2YgdHJhY3Rpb24gKHNlZSBteSByZXZpZXcgcGFwZXI6IGh0dHBzOi8vcGFwZXJzLnNzcm4uY29tL3NvbDMvcGFwZXJzLmNmbT9hYnN0cmFjdF9pZD0zNzE1NzUzKS4KSW4gdGhpcyBzZWN0aW9uLCB3ZSBicmllZmx5IGV4cGxvcmUgdGhpcyB0b3BpYy4gICAKCkZpcnN0LCBhIGdsYW5jZSBhdCB0aGUgKipkYXRhKiouIExldCdzIGxvb2sgYXQgdGhlIGRpc3RyaWJ1dGlvbiBvZiAqKkVTR19yYW5rKiogKGZyb20gU3VzdGFpbmFseXRpY3MpLgoKYGBge3IsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0KbG9hZCgiZGF0YV9lc2cuUkRhdGEiKSAjIExvYWRpbmcgdGhlIGRhdGEKZGF0YV9lc2cgJT4lCiAgbXV0YXRlKFllYXIgPSB5ZWFyKERhdGUpKSAlPiUKICBnZ3Bsb3QoYWVzKHggPSBFU0dfcmFuaywgZmlsbCA9IGFzLmZhY3RvcihZZWFyKSkpICsgCiAgZ2VvbV9oaXN0b2dyYW0oKSArIGxhYnMoZmlsbCA9ICJZZWFyIikgKyB0aGVtZV9saWdodCgpCmBgYAoKVGhlcmUgYXJlIGZldyBmaXJtcyB3aXRoIGV4dHJlbWUgRVNHX3JhbmsgKGJlbG93IDEwIG9yIGFib3ZlIDkwKS4KCkxldCdzIGNvbnRpbnVlIHdpdGggYSAic2ltcGxlIiBwaXBpbmcgZmxvdyB0aGF0IGNyZWF0ZXMgYSBjb21wYWN0IGRhdGFzZXQuCgpgYGB7ciwgbWVzc2FnZSA9IEYsIHdhcm5pbmcgPSBGfQpkYXRhX2VzZzIgPC0gZGF0YV9lc2cgJT4lCiAgc2VsZWN0KFRpY2ssIERhdGUsIENsb3NlLCBFU0dfcmFuaykgJT4lICAgICAgICAgICAgIyBLZWVwIHJlbGV2YW50IGNvbHVtbnMKICBmaWx0ZXIoRGF0ZSA+ICIyMDE0LTAyLTAxIikgJT4lICAgICAgICAgICAgICAgICAgICAjIERhdGEgYXZhaWxhYmxlIGFmdGVyIDIwMTQtMDItMDEKICBncm91cF9ieShUaWNrKSAlPiUKICBtdXRhdGUoUmV0dXJuID0gZHBseXI6OmxlYWQoQ2xvc2UpL0Nsb3NlIC0gMSkgJT4lICAjIEZvcndhcmQgcmV0dXJuCiAgdW5ncm91cCgpICU+JQogIGdyb3VwX2J5KERhdGUpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgRm9yIGVhY2ggZGF0ZTogY3JlYXRlIEVTRyBncm91cHMKICBtdXRhdGUoRVNHX2dyb3VwID0gaWZfZWxzZShFU0dfcmFuayA+IG1lZGlhbihFU0dfcmFuayksICJIaWdoX0VTRyIsICJMb3dfRVNHIikpICU+JQogIHVuZ3JvdXAoKQpkYXRhX2VzZzIKYGBgCgpCYXNlZCBvbiB0aGlzIHNob3J0IGRhdGFzZXQsIGxldCdzIGhhdmUgYSBxdWljayBsb29rIGF0IHRoZSBwZXJmIG9mIHRoZSAyIGdyb3VwcyAoaGlnaCBFU0cgdmVyc3VzIGxvdyBFU0cpLgoKYGBge3IsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0KZGF0YV9lc2cyICU+JQogIGdyb3VwX2J5KERhdGUsIEVTR19ncm91cCkgJT4lCiAgc3VtbWFyaXNlKFJldHVybiA9IG1lYW4oUmV0dXJuLCBuYS5ybSA9IFQpKSAlPiUKICBncm91cF9ieShFU0dfZ3JvdXApICU+JQogIHN1bW1hcmlzZShhdmdfcmV0dXJuID0gbWVhbihSZXR1cm4sIG5hLnJtID0gVCksICAjIEJlIGNhcmVmdWwgd2l0aCBuYS5ybSA9IFQKICAgICAgICAgICAgdm9sID0gc2QoUmV0dXJuLCBuYS5ybSA9IFQpLAogICAgICAgICAgICBTUiA9IGF2Z19yZXR1cm4vdm9sKQpgYGAKClR3byBjb25jbHVzaW9uczogICAKMS4gKipIaWdoIEVTRyoqIGRvZXMgc2xpZ2h0bHkgYmV0dGVyLiAgICAKMi4gQnV0IHRoZSBkaWZmZXJlbmNlIGlzIG5vdCBodWdlICgqdCotc3RhdCA9PiBleGVyY2lzZSEpCgpGcm9tIGluZGl2aWR1YWwgYW5udWFsIHJldHVybnM6IGlzIHRoZXJlIGFyZSBwYXR0ZXJuPwoKYGBge3IsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0KZGF0YV9lc2cyICU+JQogIG11dGF0ZShZZWFyID0geWVhcihEYXRlKSkgJT4lCiAgZ3JvdXBfYnkoWWVhciwgVGljaykgJT4lCiAgc3VtbWFyaXNlKGF2Z19FU0cgPSBtZWFuKEVTR19yYW5rLCBuYS5ybSA9IFQpLAogICAgICAgICAgICBhdmdfcmV0dXJuID0gbWVhbihSZXR1cm4sIG5hLnJtID0gVCkpICU+JQogIGdncGxvdChhZXMoeCA9IGF2Z19FU0csIHkgPSBhdmdfcmV0dXJuKSkgKyBnZW9tX3BvaW50KGFscGhhID0gMC4zKSArCiAgZ2VvbV9zbW9vdGgobWV0aG9kID0gImxtIikgKyB0aGVtZV9saWdodCgpCmBgYAoKTm8gcGF0dGVybiBhdCBhbGwsIGl0IHNlZW1zLi4uCgpMZXQncyBkaWcgZGVlcGVyIGFuZCBoYXZlIGEgbG9vayBhdCBzY3JlZW5pbmcvc2VsZWN0aW9uIGludGVuc2l0eS4KV2UgY29tcHV0ZSB0aGUgYXZlcmFnZSByZXR1cm5zIG9mIGZpcm1zIHRoYXQgaGF2ZSBFU0dfcmFuayBhYm92ZSBhIGdpdmVuIHRocmVzaG9sZC4KVG8gZG8gdGhhdCwgbGV0J3MgbWFrZSBhIGZ1bmN0aW9uLgoKYGBge3IsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0KbGlicmFyeShzY2FsZXMpICMgVGhpcyB3aWxsIGJlIHVzZWQgaW4gdGhlIHBsb3QgYmVsb3cgdG8gem9vbSBvbiB0aGUgdmFsdWVzIHdpdGggc3BlY2lhbCBsaW1pdHMKRVNHX2ltcGFjdCA8LSBmdW5jdGlvbihsZXZlbCwgZGF0YV9lc2cyKXsKICBkYXRhX2VzZzIgJT4lCiAgICBmaWx0ZXIoRVNHX3JhbmsgPiBsZXZlbCkgJT4lICAgIyBGaWx0ZXIgdG8ga2VlcCBvbmx5IHRoZSBmaXJtcyB3aXRoIEVTRyA+IGxldmVsCiAgICBwdWxsKFJldHVybikgJT4lCiAgICBtZWFuKG5hLnJtID0gVCkKfQoKbGV2ZWxfZXNnIDwtIDEwKigxOjkpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBFU0dfcmFuayB0aHJlc2hvbGQKbWFwX2RibChsZXZlbF9lc2csIEVTR19pbXBhY3QsIGRhdGFfZXNnMiA9IGRhdGFfZXNnMikgIyBUaGUgcmF3IHJlc3VsdApsZXZlbF9lc2cgJT4lCiAgYmluZF9jb2xzKHJldHVybiA9IG1hcF9kYmwobGV2ZWxfZXNnLCBFU0dfaW1wYWN0LCBkYXRhX2VzZzIgPSBkYXRhX2VzZzIpKSAlPiUKICBnZ3Bsb3QoYWVzKHggPSBsZXZlbF9lc2csIHkgPSByZXR1cm4pKSArIGdlb21fY29sKGFscGhhID0gMC41KSArIAogIHRoZW1lX2xpZ2h0KCkgKyBzY2FsZV95X2NvbnRpbnVvdXMobGltaXRzPWMoMC4wMDgsMC4wMTIpLCBvb2IgPSByZXNjYWxlX25vbmUpCmBgYAoKT3ZlcmFsbCwgKipoaWdoZXIgRVNHKiogc2VsZWN0aW9uIHNlZW1zIHByb21pc2luZyBpbmRlZWQgKGJ1dCBsZXQncyBub3QganVtcCB0byBnZW5lcmFsIGNvbmNsdXNpb25zKS4KRmluYWxseSwgbGV0J3MgaGF2ZSBhIGxvb2sgYXQgbW9yZSBob21vZ2VuZW91cyBncm91cHMuCldlIG5lZWQgZGlmZmVyZW50IHJlZmVyZW5jZSBwb2ludHMgKGxldmVsX2VzZykgYmVjYXVzZSBvZiB0aGUgZGlzdHJpYnV0aW9uIG9mIEVTR19yYW5rLgoKCmBgYHtyfQpFU0dfcXVhbnQgPC0gZnVuY3Rpb24obGV2ZWwsIHdpZHRoLCBkYXRhX2VzZzIpeyAjIEEgbmV3IGZ1bmN0aW9uCiAgZGF0YV9lc2cyICU+JQogICAgZmlsdGVyKEVTR19yYW5rID4gbGV2ZWwgLSB3aWR0aC8yLAogICAgICAgICAgIEVTR19yYW5rIDwgbGV2ZWwgKyB3aWR0aC8yKSAlPiUgICAgICMgRmlsdGVyIHRvIGtlZXAgZmlybXMgd2l0aCBFU0cgYXJvdW5kIGxldmVsCiAgICBwdWxsKFJldHVybikgJT4lCiAgICBtZWFuKG5hLnJtID0gVCkKfQpsZXZlbF9lc2cgPC0gcXVhbnRpbGUoZGF0YV9lc2ckRVNHX3JhbmssIHNlcSgwLjEsMC45LCBieSA9IDAuMSkpCmxldmVsX2VzZyAlPiUKICBiaW5kX2NvbHMocmV0dXJuID0gbWFwX2RibChsZXZlbF9lc2csIEVTR19xdWFudCwgd2lkdGggPSAxMCwgZGF0YV9lc2cyID0gZGF0YV9lc2cyKSkgJT4lCiAgZ2dwbG90KGFlcyh4ID0gbGV2ZWxfZXNnLCB5ID0gcmV0dXJuKSkgKyBnZW9tX2NvbChhbHBoYSA9IDAuNSkgKyAKICB0aGVtZV9saWdodCgpICsgc2NhbGVfeV9jb250aW51b3VzKGxpbWl0cz1jKDAuMDA3LDAuMDEyNSksIG9vYiA9IHJlc2NhbGVfbm9uZSkKYGBgCgpUaGUgZWZmZWN0IGlzIG5vdCBtb25vdG9uaWM6IHRoaW5ncyBhcmUgbm90IHRoYXQgc2ltcGxlLi4uCgojIEV4ZXJjaXNlcwoKIyMgUm9sbGluZyB3aW5kb3cKCkNoYW5nZSB0aGUgbWFpbiBsb29wIHNvIHRoYXQgb25seSA2MCBwb2ludHMgb2YgZGF0YSBhcmUgZ2l2ZW4gdG8gdGhlIHdlaWdodGluZyBzY2hlbWUocykuIFNpeHR5IHBvaW50cyBhbW91bnQgdG8gNSB5ZWFycyBvZiBtb250aGx5IGRhdGEuCgoKYGBge3IgeW91ciB0dXJuIX0KCmBgYAoKCiMjIE90aGVyIHBlcmZvcm1hbmNlIG1ldHJpY3MKVXNpbmcgdGhlICpQZXJmb3JtYW5jZUFuYWx5dGljcyogcGFja2FnZSAoaW5zdGFsbCBpdCBmaXJzdCEpLCBjb21wdXRlIHRoZSBtYXhpbXVtIGRyYXdkb3duIHZpYToKaHR0cHM6Ly93d3cucmRvY3VtZW50YXRpb24ub3JnL3BhY2thZ2VzL1BlcmZvcm1hbmNlQW5hbHl0aWNzL3ZlcnNpb25zLzEuNS4yL3RvcGljcy9tYXhEcmF3ZG93bgoKQ29tcHV0ZSB0aGUgdHJhbnNhY3Rpb24gY29zdC1hZGp1c3RlZCBTUjogJFRDLVNSPShcYmFye3J9LTAuMDA1KlR1cm4pL1xzaWdtYSQuCgpBZGQgYm90aCBtZXRyaWNzIHRvIHRoZSBwZXJmX21ldCgpIGZ1bmN0aW9uLgoKIyMgTWluaW11bSB2YXJpYW5jZQpBZGQgdGhlIE1WIHBvcnRmb2xpbyB0byB0aGUgc2V0IG9mIHN0cmF0ZWdpZXMuIFRoZSB3ZWlnaHRzIGRlcGVuZCBvbmx5IG9uIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeDogJHc9XGZyYWN7XFNpZ21hXnstMX0xfXsxJ1xTaWdtYV57LTF9MX0kLgoKIyMgbWFwKCkgZXhwZXJ0aXNlCkV4dGVuZCB0aGUgbWFwKCkgc3ludGF4IHRvIHRoZSBjYXNlIHdpdGggbWFueSBzdHJhdGVnaWVzLiBCT05VUzogaGF2ZSBhIGxvb2sgYXQgcG1hcCgpIQoKIyMgUmVhbGlzdGljIHBvcnRmb2xpb3MKSW4gcHJhY3RpY2UsIG1hbnkgc2F2ZWd1YXJkcyBhcmUgYXBwbGllZCwgaWYgb25seSB0byByZWR1Y2UgdHVybm92ZXIuIE9uZSBzdWNoIGV4YW1wbGUgaXMgYm94IGNvbnN0cmFpbnQ6IHRoZSB3ZWlnaHRzIGluIHRoZSBwb3J0Zm9saW8gbXVzdCBub3QgbGllIGFib3ZlIG9yIGJlbG93IHVzZXItc3BlY2lmaWVkIHRocmVzaG9sZHMuIAoKSW4gbWluaW11bSB2YXJpYW5jZSwgaXQgaXMgcG9zc2libGUgdG8gcmVkdWNlIGxldmVyYWdlIGJ5IHNocmlua2luZyB0aGUgY292YXJpYW5jZSBtYXRyaXggdG93YXJkcyB0aGUgaWRlbnRpdHkgZnVuY3Rpb25zOgokJFxTaWdtYV4qPSgxLVxhbHBoYSkgXFNpZ21hXlMrXGFscGhhIEksJCQKd2hlcmUgJFxTaWdtYV5TJCBpcyB0aGUgc2FtcGxlIGNvdmFyaWFuY2UgbWF0cml4IGFuZCAkSSQgdGhlIGlkZW50aXR5IG1hdHJpeC4gQXMgJFxhbHBoYSQgaW5jcmVhc2VzIHRvIDEsIHRoZSB3ZWlnaHRzIGNvbnZlcmdlIHRvIHRoZSBlcXVhbGx5LXdlaWdodGVkIHBvcnRmb2xpby4K